题目传送门(BZOJ)

题解 :

首先令 n > m
从题目中给的式子可以比较明显的看出, 这是一个杨辉三角的形式
最短路一定是从 (0, 0)(n, 0) 再到 (n, m)
因为从平面内部跳, 一定可以找到一一对应的比该路径权值小的点, 故其不优
所以本题就变成了在杨辉三角上的两条斜线求和
1
1\;\;1
1\;\;2\;\;1
1\;\;3\;\;3\;\;1
1\;\;4\;\;6\;\;4\;\;1
1\;\;5\;\;10\;10\;5\;\;1
1\;\;6\;\;15\;20\;15\;6\;\;1
可以发现从 C_{x}^{0}C_{x+k}^{k} 的某条斜线上的和, 等于 C_{x+k+1}^{k+1}
这个利用杨辉三角的递推式就可以比较方便的证明,
由于难于打出来, 这里就不做证明了, 看上去也挺好看出来的
回到题中 ,第一条斜线全是 1, 给答案一共贡献了 n
第二条斜线则恰好是 C_{n+m+1}^{m}
本题就变成了计算一个组合数
由于 n\times m \le 10^{12}, 且我们规定 n \ge m
所以, m\le 10^6
把组合数式子展开得到 :
C_{n+m+1}^{m} = \frac{(n+m+1)!}{(m)!\times (n+1)!}
(n+m+1)!(n+1)! 约一下可得
\frac{(n+2)\times (n+3)\times (n+4)\times \cdots \times (n+m+1)}{m!}
分数线上下都是 m 项, 复杂度是求 m! 的逆元的 O(m\log p)

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int p = 1e9+7;#define ll long long ll qp(ll x, int y) { ll res = 1; for(; y; y >>= 1, x = x*x%p) if(y&1) res = res*x%p; return res;}int main() { ll n, m; scanf("%lld%lld", &n, &m); if(n < m) swap(n, m); n = (n+m+1)%p; ll num = 1, den = 1; for(int i = 1; i <= m; i ++ ) { num = num*(n-i+1)%p; den = den*i%p; } printf("%lld\n", (num*qp(den, p-2)+n-m-1)%p); getchar(), getchar();}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<