http://acm.hdu.edu.cn/showproblem.php?pid=5698
刚开始计算了下，就是当前位置等于其左边的值加上上边的值，于是写了个二维数组，dp[2][100005]，进行存储，然后复杂度为o(n*m)，超时了
于是，杨神牛，提醒了我说杨辉三角，然后，写了个组合数取模，但当组合数比较大时，计算的组合数取模不对
百度了下大组合数取模，然后，知道转化为阶乘来算，用上LUCAS定理，乘法逆元，快速幂
LUCAS定理: Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
乘法逆元：
(a/b)%mod ，其实如果mod是质数的时候可以用费马小定理来做，即
a*b^(mod-2)//这个比较常用
1 #include <cmath> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 #include <memory> 7 #include <string> 8 #include <queue> 9 #include <map> 10 #include <stdio.h> 11 #include <vector> 12 #include <stack> 13 #include <fstream> 14 #include <set> 15 #define N 200005 16 #define mod 1000000007 17 using namespace std; 18 long long mod_pow(int a,int n,int p) 19 { 20 long long ret=1; 21 long long A=a; 22 while(n) 23 { 24 if (n & 1) 25 ret=(ret*A)%p; 26 A=(A*A)%p; 27 n>>=1; 28 } 29 return ret; 30 } 31 32 long long factorial[N]; 33 34 void init() 35 { 36 factorial[0] = 1; 37 for(int i = 1;i <= N;i++) 38 factorial[i] = factorial[i-1]*i%mod; 39 } 40 41 long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大为10^5。a,b可以很大！ 42 { 43 long long re = 1; 44 while(a && k) 45 { 46 long long aa = a%p;long long bb = k%p; 47 if(aa < bb) return 0; 48 re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p; 49 a /= p; 50 k /= p; 51 } 52 return re; 53 } 54 int main() 55 { 56 //freopen("in.txt","r",stdin); 57 init(); 58 int n,m; 59 while(cin>>n>>m) 60 { 61 if(n==2&&m==2) 62 { 63 cout<<1<<endl; 64 } 65 else 66 { 67 cout<<Lucas(n+m-4,m-2,mod)<<endl; 68 } 69 } 70 return 0; 71 }