题目:给定一个多项式$(ax+by)^k$,请求出多项式展开后$(x^ny^m)$的系数
由2项式展开 $(ax+by)^k$ = $\sum_{i=0}^\{i=k} \{C_{k}^\{i} a^ib^{k-i} x^iy^{k-i}}$
$a^i$可以使用快速幂算法求解
关键难点是求$C_k^i= \frac{ n*(n-1)…(n-i+1)}{i!}$
看上去是可以直接求,但除法的开销太大,时间上来不及
应用费马小定理
如果p是一个质数,而整数a不是p的倍数,
则有 $a^{p-1}\equiv 1$ (mod p)
即 $ aa^{p-2}\equiv 1$ 即
所以 a的逆元是 $a^{p-2}$
因为 ab=$\Theta$ 其中 $\Theta$是幺元,所以 b是a的逆元
如 $x/b=xa$除一个等于乘以它的逆元
此题种 p==10007是质数
$aa^{10005}\equiv1$
$x/a$ = $x$$a^{10005}$
参考 我要出去乱说
#include<iostream>
using namespace std;
typedef long long LL;
const int mod=10007;
int qmi(int a,int k)
{
a=a%mod;
int res=1;
while(k)
{
if(k&1)res=res*a%mod;
a=a*a%mod;
k=k>>1;
}
return res;
}
int main()
{
int a,b,k,m,n;
cin>>a>>b>>k>>n>>m;
int res=qmi(a,n)*qmi(b,m)%mod;
for(int i=1,j=k;i<=n;i++,j--)
{
res=res*j%mod;//*k
res=res*qmi(i,mod-2)%mod;
}
cout<<res<<endl;
}
过年还这么努力啊?