RETOI Round2 非官方题解

即为统计每个坐标和为质数的贡献和。

因为任何合法一条路径不可能同时通过两个坐标和相等的坐标，而且每一条路径必定通过一个坐标 $x,y$，$x+y=p,p\in prime,1\le p\le n+m-2$。
所以对于 $\forall p\in prime,1\le p\le n+m-2$，满足 $val_p=C_{n+m-2}^{n-1}$，$val_p$ 即为 $p$ 的总贡献。

统计质数个数即可，复杂度 $O(n+m)$。
代码不放了。