BZOJ 2886/3260: 跳 – [组合数学]

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