数学：Lucas定理

利用Lucas定理解决大组合数取模

Lucas定理是用来求 C(n,m) mod p，p为素数的值。（注意：p一定是素数）

Lucas定理用来解决大组合数求模是很有用的

Lucas定理最大的数据处理能力是p在10^5左右

表达式：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

递归方程：(C(n%p, m%p)*Lucas(n/p, m/p))%p。（递归出口为m==0，return 1）

然后来一道裸题

BZOJ2982

 1 #include<cstdio>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
 7     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int n,m,p=10007;
11 int qpow(int a,int b)  //快速幂 
12 {
13     int ans;
14     for(ans=1;b;b>>=1,a=a*a%p)
15         if(b&1) ans=ans*a%p;
16     return ans; 
17 }
18 int getc(int n,int m)
19 {
20     if(n<m) return 0;
21     if(m>n-m) m=n-m;
22     long long s1=1,s2=1;
23     for(int i=0;i<m;i++)
24     {
25         s1=s1*(n-i)%p;
26         s2=s2*(i+1)%p;
27     }
28     return s1*qpow(s2,p-2)%p;
29 }
30 int lucas(int n,int m)
31 {
32     if(m==0) return 1;
33     return getc(n%p,m%p)*lucas(n/p,m/p)%p;
34 }
35 int main()
36 {
37     int T;
38     T=read();
39     while(T--)
40     {
41         n=read();m=read();
42         printf("%d
",lucas(n,m));
43     }
44     return 0;
45 }

大赞快速幂