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)$。
补丁：本人用的是埃氏筛，复杂度 $O((n+m)loglog(n+m))$，但可以用 bitset 优化到 $O(\frac{(n+m)loglog(n+m)}{w})$，有兴趣可以自行学习。
代码不放了。