洛谷P1313计算系数（数学二项式次方展开定理，快速幂，除法取模逆元）

题目链接：https://www.luogu.org/problemnew/show/P1313

我们要知道，平常的平方展开x*x+2*x*y+y*y其实本质就是二项式定理展开，现在扩展到n次方也是一样套路，不要不知所措。

这一项就是C(k,m)*(ax)^(k-m)*(by)^m，那么很容易知道系数就是C(k,m)*a^(k-m)*b^m；

两个次方很好求，关键是求组合数。

因为有除法取模，所以要用到逆元。（好像也可以递推求组合数C(k,m)=C(k-1,m-1)+C(k-1,m)这里就不说了）

 1 //数学二项式定理(展开n次方项)+快速幂求组合数
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int mod=10007;
 7 const int maxn=1e6+5;
 8 int a,b,k,n,m;
 9 
10 ll Qpow(ll a,ll b)
11 {
12     ll r=1;
13     while(b)
14     {
15         if(b%2==1) r=r*a%mod;
16         a=a*a%mod;
17         b/=2;
18     }
19 
20     return r;
21 }
22 
23 int main()
24 {
25     ios::sync_with_stdio(false); cin.tie(0);
26 
27     cin>>a>>b>>k>>n>>m;
28 
29     ll B=Qpow(b,m);
30     ll A=Qpow(a,k-m);//是k-m,不是n-m!
31 
32     ll fm=1; for(ll i=m;i>=1;i--) fm=fm*i%mod;//m阶乘
33     ll niyuan=Qpow(fm,mod-2);//m阶乘逆元
34     ll fz=1; while(m--) fz=fz*(k--)%mod;//分子阶乘n*(n-1)...(n-m+1)
35     ll C=fz*niyuan;//组合数C(k,m);
36 
37     //cout<<B<<' '<<A<<' '<<C<<endl;
38     ll ans=B*A*C%mod;
39     cout<<ans<<endl;
40 
41     return 0;
42 }

完。