题目传送门(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原创, 转载必须以链接形式注明>原文链接<