求组合数公式

for (int i=0;i<=n;i++){ for (int j=0;j<=i;j++){ if (j==0){ dp[i][j]=1; //n个数中取0个,默认为1 } else{ dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%p; } } }
讯享网
由于需要用到二重循环,因此此方法适用的范围是: n,m < = 10^4 左右
时间复杂度:O(n^2)
快速幂+乘法逆元
费马小定理:如果 p 是一个质数,并且 a 和 p 互质,则满足: a^(p − 1) ≡ 1 ( mod p )
乘法逆元:如果 a 与 p 都是质数,并且满足同余方程式:a ⋅ x ≡ 1 ( m o d p ) 则称 x 为 a 模 p 的乘法逆元,即:1 / (a mod p) = x
将费马小定理进行转化,得到: a ⋅ a^(p − 2) ≡ 1 (mod p)
则如果 a 和 p 都是质数,x = a^(p − 2) x 就是 a 模 p 的乘法逆元。


讯享网f[0]=g[0]=1; //初始值 for (int i=1;i<=n;i++){ f[i]=f[i-1]*i%p; //计算i的阶乘 g[i]=g[i-1]*qpow(i,p-2)%p; //计算i的乘法逆元 qpow为快速幂 } ... int get(int n,int m){ //得到C(n,m)的组合数答案 return f[n]*g[m]*g[n-m]%p; }
高精度组合数
如果我们需要求 组合数 而不需要求其模数,我们可以发现这个数字将会变得非常大,因为组合数的增长是非常快的!此时我们必须要采用高精度的方法。
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=5010; int primes[N],cnt; int sum[N]; bool st[N]; void get_primes(int n) { for(int i=2;i<=n;i++) { if(!st[i])primes[cnt++]=i; for(int j=0;primes[j]*i<=n;j++) { st[primes[j]*i]=true; if(i%primes[j]==0)break;//==0每次漏 } } } // 对p的各个<=a的次数算整除下取整倍数 int get(int n,int p) { int res =0; while(n) { res+=n/p; n/=p; } return res; } //高精度乘 vector<int> mul(vector<int> a, int b) { vector<int> c; int t = 0; for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; c.push_back(t % 10); t /= 10; } while (t) { c.push_back(t % 10); t /= 10; } // while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行 return c; } int main() { int a,b; cin >> a >> b; get_primes(a); for(int i=0;i<cnt;i++) { int p = primes[i]; sum[i] = get(a,p)-get(a-b,p)-get(b,p);//是a-b不是b-a } vector<int> res; res.push_back(1); for (int i = 0; i < cnt; i ++ ) for (int j = 0; j < sum[i]; j ++ )//primes[i]的次数 res = mul(res, primes[i]); for (int i = res.size() - 1; i >= 0; i -- )cout<<res[i]<<" "; return 0; }
卢卡斯定理
此方法用于非常大的 n 和 m ,但是 p 却比较小的计算。
然后注意到 p 是一个质数,因此 n 和 m对其取余后,最后的结果一定比 p 小。
因此就可以对第二个式子进行 快速幂+逆元 的方法,我们知道这个方法的瓶颈是过大的 n 导致空间不够或者循环过大,通过这种方法缩小后便可以直接使用此方法。
讯享网f[0]=g[0]=1; //初始值 for (int i=1;i<=p;i++){ f[i]=f[i-1]*i%p; //计算i的阶乘 g[i]=g[i-1]*qpow(i,p-2)%p; //计算i的乘法逆元 qpow为快速幂 } ... int get(int n,int m){ //得到C(n,m)的组合数答案 return f[n]*g[m]*g[n-m]%p; } ... int lucas(int n,int m){ if (m==0){ return 1; } return lucas(n/p,m/p)*get(n%p,m%p)%p; }
此方法使用范围(大概): n , m < = 10^18 , p < = 10^6

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80648.html