1:使用杨辉三角
#include<bits/stdc++.h> using namespace std; #define int long long const int mod=10007; int a,b,k,n,m; int c[1011][1011]; void dt(int x) { c[0][0]=1; for(int j=1;j<=x;j++) //J为行 for(int i=0;i<=j;i++) //i为列 { if(i==0) c[i][j]=1; else c[i][j]=(c[i][j-1]+c[i-1][j-1])%mod; } } int dd(int x,int p) { int ans=1; while(p) { if(p%2==1) ans=ans*x%mod; p/=2; x=x*x%mod; } return ans%mod; } main(){ cin>>a>>b>>k>>n>>m; dt(k); cout<<(dd(a,n)%mod*dd(b,m)%mod*c[n][k])%mod; return 0; }
2:使用费马小定理找逆元
#include<iostream> #include<cstdio> using namespace std; long long ksm(long long a,long long b) { if(b==0) return 1; if(b%2==0) return ksm(a,b>>1)*ksm(a,b>>1)%10007; else return a*ksm(a,b>>1)*ksm(a,b>>1)%10007; } int main() { int a,b,k,n,m; scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); int x=1,y=1; for(int i=1;i<=n;i++) //算出分母的值 x=x*i%10007; for(int i=k-n+1;i<=k;i++) //算出分子的值 y=y*i%10007; //因为x^10006 mod 10007=1,于是给分子、分母分别乘上x^10005即可消去分母 y=y*ksm(x,10005)%10007; y=y*ksm(a,n)*ksm(b,m)%10007; printf("%d",y); return 0; }
3:预处理出1到N的逆元
#include<bits/stdc++.h> using namespace std; const int mod=10007; long long ni[100100]; void prepare(int x) { ni[1]=1; for (int i=2;i<=x;i++) ni[i]=(mod-mod/i)*ni[mod%i]%mod; return; } long long ksm(long long a,long long b) { if(b==0)return 1; if(b%2==0)return ksm(a,b>>1)*ksm(a,b>>1)%mod; else return a*ksm(a,b>>1)*ksm(a,b>>1)%mod; } int main() { int a,b,k,m,n; cin>>a>>b>>k>>n>>m; prepare(n); int d=1; for (int i=1;i<=n;i++) d=d*(k-i+1)%mod*ni[i]%mod; d=d*ksm(a,n)*ksm(b,m)%mod; cout<<d; }
标签:系数,int,d%,long,10007,计算,ksm,include From: https://www.cnblogs.com/cutemush/p/16757251.html