排列组合lucas模板

 1 //codeforces 559C|51nod1486 Gerald and Giant Chess(组合数学+逆元)
 2 
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 #define LL long long
 6 typedef pair<int,int> pii;
 7 const int inf = 0x3f3f3f3f;
 8 const int N =2e5+10;
 9 #define clc(a,b) memset(a,b,sizeof(a))
10 const double eps = 1e-8;
11 const int MOD = 1e9+7;
12 void fre() {freopen("in.txt","r",stdin);}
13 void freout() {freopen("out.txt","w",stdout);}
14 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
15 
16 struct Point{
17     int x,y;
18     Point(){}
19     Point(int _x,int _y):x(_x),y(_y){}
20     bool operator <(const Point &rhs) const{
21         if(x==rhs.x) return y<rhs.y;
22         return x<rhs.x;
23     }
24 }p[N];
25 
26 int f[N];
27 int invv[N];
28 int inv(int x){
29   int ret=1,y=MOD-2;
30   while(y){
31     if(y&1)ret=1ll*ret*x%MOD;
32     y>>=1;x=1ll*x*x%MOD;
33   }
34   return ret; 
35 }
36 int C(int n,int m){
37   if(n<m)return 0;
38   int ret=1ll*f[n]*invv[m]%MOD;
39   ret=1ll*ret*invv[n-m]%MOD;
40   return ret; 
41 }
42 int lucas(int n,int m){
43    if(m == 0) return 1;
44    return 1ll*C(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;
45 }
46 
47 void init(int n,int m){
48   f[0]=1;
49   invv[0]=1;
50   for(int i=1;i<=n+m+5;++i){
51     f[i]=1ll*i*f[i-1]%MOD;
52     invv[i]=inv(f[i]);
53   }
54 }
55 
56 int sum[N];
57 int main(){
58     int n,m,q;
59     scanf("%d%d%d",&n,&m,&q);
60     init(n,m);
61     for(int i=1;i<=q;i++){
62         int x,y;
63         x=read(),y=read();
64         p[i]=Point(x,y);
65     }
66     p[++q]=Point(n,m);
67     sort(p+1,p+1+q);
68     for(int i=1;i<=q;i++){
69         sum[i]=lucas(p[i].x-1+p[i].y-1,p[i].x-1);
70         for(int j=1;j<i;j++){
71             sum[i]=(sum[i]-1LL*sum[j]*lucas(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%MOD+MOD)%MOD;
72         }
73     }
74     printf("%d
",sum[q]);
75     return 0;
76 }