组合数求法

885. 求组合数 I - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int d[2010][2010];int main()
{int n;cin>>n;for(int i=0;i<=2000;i++)for(int j=0;j<=i;j++)if(j==0||j==i) d[i][j]=1;else  d[i][j]=(d[i-1][j-1]+d[i-1][j])%mod;while(n--){int a,b;cin>>a>>b;cout<<d[a][b]<<endl;}
}

886. 求组合数 II - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define  int long long 
const int mod=1e9+7;
int fact[N],infact[N];int qmi(int a,int b,int c)
{   int res=1;while(b){if(b&1) res=res*a%c;b>>=1;a=a*a%c;}return res;}signed main()
{int n;cin>>n;fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=fact[i-1]*i%mod;infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod;}while(n--){int a,b;cin>>a>>b;cout<<fact[a]*infact[b]%mod*infact[a-b]%mod;cout<<endl;}
}

887. 求组合数 III - AcWing题库

#include<bits/stdc++.h>
using namespace std;
#define int long longint qmi(int a,int b,int c)
{int res=1;while(b){if (b&1) res=res*a%c;b>>=1;a=a*a%c;}return res;
}
int ans(int a,int b,int c)
{if(b>a) return 0;int res=1;for(int i=1,j=a;i<=b;i++,j--){res=res*j%c;res=res*qmi(i,c-2,c)%c;}return res;}
int lucas(int a,int b,int c)
{if(a<c&&b<c) return ans(a,b,c);else return ans(a%c,b%c,c)*lucas(a/c,b/c,c)%c;
}signed main()
{int n;cin>>n;while(n--){int a,b,p;cin>>a>>b>>p;cout<<lucas(a,b,p)<<endl;}
}

888. 求组合数 IV - AcWing题库

#include<bits/stdc++.h>
using namespace std;const int N=5010;
bool st[N];
int prime[N],cnt=0;
int sum[N];void get_prime(int n)
{for(int i=2;i<=n;i++){ if(!st[i]) prime[cnt++]=i;for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=1;if(i%prime[j]==0) break;}}
}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;
}signed main()
{int a,b;cin>>a>>b;get_prime(a);for(int i=0;i<cnt;i++){int p = prime[i];sum[i] = get(a,p)-get(a-b,p)-get(b,p);//是a-b不是b-a}vector <int>ans;ans.push_back(1);for(int i=0;i<cnt;i++)for(int j=0;j<sum[i];j++)ans=mul(ans,prime[i]);for(int i=ans.size()-1;i>=0;i--){cout<<ans[i];}
}