lucas定理 http://www.cnblogs.com/vongang/archive/2012/12/02/2798138.html
题目:http://hihocoder.com/contest/challenge13/problem/1
彬神的方法……
假设右上方向出格子 右上方向 宽 为 w ,高 为 h,
则从 上方的格子出去可以走 0 个 横向,1 个 横向 … 到 w 个 横向,
但是所走的 是 在 那个 位置 走 那几个 横向,是从 n 个 盒子 里 放 m 个 球的问题
同理 从右边的格子出去可以走 0 个高度,1个高度……到 h 个高度
其中 n ,m 为 1 要特殊处理
由于 四个方向计算了两次 ,所以要 - 4
贴代码……
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <string> using namespace std; typedef long long ll; const double ESP = 10e-8; const int MOD = 1000000007; typedef long long LL; LL exp_mod(LL a, LL b, LL p) { LL res = 1; while(b != 0) { if(b&1) res = (res * a) % p; a = (a*a) % p; b >>= 1; } return res; } LL Comb(LL a, LL b, LL p) { if(a < b) return 0; if(a == b) return 1; if(b > a - b) b = a - b; LL ans = 1, ca = 1, cb = 1; for(LL i = 0; i < b; ++i) { ca = (ca * (a - i))%p; cb = (cb * (b - i))%p; } ans = (ca*exp_mod(cb, p - 2, p)) % p; return ans; } LL Lucas(int n, int m, int p) { LL ans = 1; while(n&&m&&ans) { ans = (ans*Comb(n%p, m%p, p)) % p; n /= p; m /= p; } return ans; } int fun(int h,int w){ int ans = 0; for(int i = 0;i <= h;i++){ ans += Lucas(w+i,i,MOD); ans %= MOD; } for(int i = 0;i < w;i++){ ans += Lucas(h+i,i,MOD); ans %= MOD; } return ans; } int main(){ // freopen("input.txt","r",stdin); int n,m,i,j; while(~scanf("%d%d%d%d",&n,&m,&i,&j)){ if(n==1){ printf("%d ",m); continue; }else if(m==1){ printf("%d ",n); continue; } int ans = fun(i-1,j-1); ans += fun(n-i,j-1); ans %= MOD; ans += fun(i-1,m-j); ans %= MOD; ans += fun(n-i,m-j); ans %= MOD; ans = (ans-4+MOD)%MOD; printf("%d ",ans); } return 0; }