组合数取模及Lucas定理

时间:2022-12-13 16:50:37

引入:

组合数C(m,n)表示在m个不同的元素中取出n个元素(不要求有序),产生的方案数。定义式:C(m,n)=m!/(n!*(m-n)!)(并不会使用LaTex QAQ)。

根据题目中对组合数的需要,有不同的计算方法。

(1)在模k的意义下求出C(i,j)(1≤j≤i≤n)共n(数量级)个组合数:

运用一个数学上的组合恒等式(OI中称之为杨辉三角):C(m,n)=C(m-1,n-1)+C(m-1,n)。

证明:

1.直接将组合数化为定义式暴力通分再合并。过程略。

2.运用组合数的含义:设m个元素中存在一个“特殊”元素a,对从m个元素中选出n个元素进行分类讨论。

第一种情况:n个元素中含有元素a,则只需在剩余m-1个元素中选出n-1个元素即可。方案数为C(m-1,n-1)。

第二种情况:n个元素中不含元素a,则只需在剩余m-1个元素中选出n个元素即可。方案数为C(m-1,n)。

这样我们就得到了一个与组合数有关的递推式,初始化C(i,0)=1,随后通过递推以O(n2)的复杂度完成计算。均摊O(1)。

例题:NOIP2016 D2T1 组合数问题 题目链接

题意:给定一个数k,然后给出t组m,n,对于每一组数据,询问对于C(i,j)(0≤i≤n,0≤j≤min(i,m)),有多少个C(i,j)是k的倍数。

数据范围:k≤21,m,n≤2000,t≤10000。子任务见题目链接。

题解:

70分做法:O(20002)预处理出所有组合数,然后每次暴力扫描C(i,j)判断是否是k的倍数。然后机智地忘记取模(没错就是我233)

90分做法:在原有70分做法的预处理中加上取模,暴力扫描判断是否为0。

100分做法:发现每次只是数据范围改变,k和组合数都没有改变,所以尝试优化重复操作。

预处理+取模后,问题变为在整张组合数表中某个范围内0的个数。我们将非0数置0,将0置1,问题转化为矩阵和。用前缀和预处理可以做到O(1)查询。

代码:

组合数取模及Lucas定理组合数取模及Lucas定理
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2000+10;
 4 int c[maxn][maxn],d[maxn][maxn],s[maxn][maxn];
 5 int t,n,m,k;
 6 int main()
 7 {
 8     int i,j;
 9     cin>>t>>k;
10     for(i=0;i<maxn;i++){c[i][0]=c[i][i]=1;}
11     for(i=1;i<maxn;i++){for(j=1;j<i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;}}
12     for(i=0;i<maxn;i++){for(j=i+1;j<maxn;j++){c[i][j]=1;}}
13     for(i=0;i<maxn;i++){for(j=0;j<maxn;j++){if(c[i][j]){d[i][j]=0;}else{d[i][j]=1;}}}
14     for(i=0;i<maxn;i++){s[i][0]=s[i-1][0]+d[i][0];s[0][i]=s[0][i-1]+d[0][i];} 
15     for(i=1;i<maxn;i++){for(j=1;j<maxn;j++){s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+d[i][j];}}
16     while(t--)
17     {
18         int ans=0;
19         scanf("%d%d",&n,&m);
20         //for(i=0;i<=n;i++){for(j=0;j<=min(i,m);j++){if(!c[i][j]){ans++;}}}
21         //cout<<ans<<endl;
22         printf("%d\n",s[n][m]);
23     }
24     return 0;
25 }
View Code

 

(2)在模p的意义下求出C(n,i)(0≤i≤n<p)共n个组合数:

此时在组合数之间无法递推,只能用定义式计算:C(n,i)=n!/(i!*(n-i)!)。

O(n)求出1~n的逆元,并通过前缀积O(n)求得1~n的阶乘及其逆元,对于每个组合数O(1)计算。

并不能算例题的例题:Luogu T7468 I liked Matrix! 题目链接

题目描述:在一个n*m 的矩阵A 的所有位置中随机填入0 或1,概率比为x : y。令B[i]=a[i][1]+a[i][2]+......+a[i][m],求min{B[i]}的期望,并将期望乘以(x + y)^nm 后对1e9+7取模。

数据范围:

对于20% 的数据:n,m,x,y<=3

对于40% 的数据:n,m,x,y<= 70

对于70% 的数据:n,m,x,y<=5000

对于100% 的数据:n,m,x,y<=200000

题解:

20%的直接暴力枚举每个格子x次0,y次1,求出每次min{B[i]}并求和。

40%和70%好像可以用不同的DP来做,DP蒟蒻表示不会......

100分做法:先挖个坑在这 到时候写一个解题报告(虽然并不会写部分分)

(3)在模p(p为质数)的意义下求出C(n,m)(2≤p≤n,m)

此时n,m一般可以出到max long long,简单地O(n)预处理无法接受。就算n,m较小,p比n,m小时定义式中n!和m!在模p的意义下都为0,由于0不存在逆元,故直接用逆元计算会出错。此时需要用Lucas定理递归计算。

Lucas定理:

C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)。第一部分递归计算,第二部分用逆元处理。特别地,当递归过程中出现C(n,m),m>n的情况时,规定C(n,m)=0。

这个定理的另一个表述:C(n,m)%p等价于将n,m写成p进制,对n,m上的每一位进行组合数运算。

例题:Luogu P3807 【模板】卢卡斯定理 题目链接

题解:裸的Lucas。

代码:

组合数取模及Lucas定理组合数取模及Lucas定理
 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 using namespace std;
 4 const int maxn=2e5+10;
 5 LL fac[maxn],infac[maxn],inv[maxn];
 6 int n,m,p,t;LL ans;
 7 LL f(int n,int m,int p)
 8 {
 9     if(m>n){return 0;}
10     return fac[n]*infac[n-m]%p*infac[m]%p;
11 }
12 LL lucas(int n,int m,int p)
13 {
14     if(!m){return 1;}
15     return f(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
16 }
17 int main()
18 {
19     int i,j;
20     cin>>t;
21     while(t--)
22     {
23         cin>>n>>m>>p;
24         fac[0]=infac[0]=1;infac[1]=inv[1]=1;
25         for(i=1;i<p;i++){fac[i]=i%p*fac[i-1]%p;}
26         for(i=2;i<p;i++){inv[i]=(p-p/i*inv[p%i]%p)%p;}
27         for(i=2;i<p;i++){infac[i]=inv[i]*infac[i-1]%p;}
28         printf("%lld\n",lucas(n+m,m,p));
29     }
30     return 0;
31 }
View Code

 

(4)在模p(p不一定为质数)的意义下求出C(n,m):

此时p不一定为质数,无法直接运用Lucas定理求解,可以将p进行质因数分解,对每个质因子进行Lucas,到时候再用中国剩余定理合并。质因数分解建议采用Pollard Rho算法。