即为统计每个坐标和为质数的贡献和。 因为任何合法一条路径不可能同时通过两个坐标和相等的坐标，而且每一条路径必定通过一个坐标 x,yx,yx,y，x+y=p,p∈prime,1≤p≤n+m−2x+y=p,p\in prime,1\le p\le n+m-2x+y=p,p∈prime,1≤p≤n+m−2。 所以对于 ∀p∈prime,1≤p≤n+m−2\forall p\in prime,1\le p\le n+m-2∀p∈prime,1≤p≤n+m−2，满足 valp=****−2n−1val_p=C_{n+m-2}^{n-1}valp =****−2n−1 ，valpval_pvalp 即为 ppp 的总贡献。 统计质数个数即可，复杂度 O(n+m)O(n+m)O(n+m)。 补丁：本人用的是埃氏筛，复杂度 O((n+m)loglog(n+m))O((n+m)loglog(n+m))O((n+m)loglog(n+m))，但可以用 bitset 优化到 O((n+m)loglog(n+m)w)O(\frac{(n+m)loglog(n+m)}{w})O(w(n+m)loglog(n+m) )，有兴趣可以自行学习。 代码不放了。