首页 > 代码库 > 求组合数
求组合数
第一类时mod为素数
1 typedef long long LL; 2 3 LL n,m,p; 4 5 LL quick_mod(LL a, LL b) 6 { 7 LL ans = 1; 8 a %= p; 9 while(b)10 {11 if(b & 1)12 {13 ans = ans * a % p;14 b--;15 }16 b >>= 1;17 a = a * a % p;18 }19 return ans;20 }21 22 LL C(LL n, LL m)23 {24 if(m > n) return 0;25 LL ans = 1;26 for(int i=1; i<=m; i++)27 {28 LL a = (n + i - m) % p;29 LL b = i % p;30 ans = ans * (a * quick_mod(b, p-2) % p) % p;31 }32 return ans;33 }34 35 LL Lucas(LL n, LL m)36 {37 if(m == 0) return 1;38 return C(n % p, m % p) * Lucas(n / p, m / p) % p;39 }
第二类时mod可以为合数
1 typedef long long LL; 2 const int N = 200005; 3 4 bool prime[N]; 5 int p[N]; 6 int cnt; 7 8 void isprime() 9 {10 cnt = 0;11 memset(prime,true,sizeof(prime));12 for(int i=2; i<N; i++)13 {14 if(prime[i])15 {16 p[cnt++] = i;17 for(int j=i+i; j<N; j+=i)18 prime[j] = false;19 }20 }21 }22 23 LL quick_mod(LL a,LL b,LL m)24 {25 LL ans = 1;26 a %= m;27 while(b)28 {29 if(b & 1)30 {31 ans = ans * a % m;32 b--;33 }34 b >>= 1;35 a = a * a % m;36 }37 return ans;38 }39 40 LL Work(LL n,LL p)41 {42 LL ans = 0;43 while(n)44 {45 ans += n / p;46 n /= p;47 }48 return ans;49 }50 51 LL Solve(LL n,LL m,LL P)52 {53 LL ans = 1;54 for(int i=0; i<cnt && p[i]<=n; i++)55 {56 LL x = Work(n, p[i]);57 LL y = Work(n - m, p[i]);58 LL z = Work(m, p[i]);59 x -= (y + z);60 ans *= quick_mod(p[i],x,P);61 ans %= P;62 }63 return ans;64 }65 66 int main()67 {68 int T;69 isprime();70 cin>>T;71 while(T--)72 {73 LL n,m,P;74 cin>>n>>m>>P;75 n += m - 2;76 m--;77 cout<<Solve(n,m,P)<<endl;78 }79 return 0;80 }
求组合数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。