题解：P1313 [NOIP2011 提高组] 计算系数
4041nofoundGeoge
·
·
题解
## 公式推导
大佬们的公式太复杂。让我这个蒟蒻好好推导一下。
首先，我们来看几个多项式展开：
$$
(a+b)^2=1a^2+2ab+1b^2
$$
$$
(a+b)^3=1a^3 + 3a^2b + 3ab^2 + 1b^3
$$
$$
(a+b)^4=1a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + 1b^4
$$
$$
(a+b)^5=1a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + 1b^5
$$
我们可以发现，每一项系数都以某种规律排列，每一项而指数的和都为展开前的指数。
然而这种规律就是杨辉三角的数列。杨辉三角可以写成组合数 $C^n_m$ 的形式（其中 $C^n_m$ 也可写作 ${m \choose n}$，表示 $\dfrac{n!}{m!(n-m)!}$，其中 $x!=\prod\limits^x_{i=1}i=x(x-1)(x-2)\dots1$，特别地 $0!=1$），所以我们可以得出：
$$
(a+b)^k=C^0_ka^kb^0+C^{1}_ka^{k-1}b^1+C^2_ka^{k-2}b^2+\dots+C^{k}_{k}a^0b^k
$$
我们用 $\sum$ 列出通项公式。
$$
(a+b)^k = \sum_{n=0}^{k} C^{n}_{k} a^{k-n} b^n
$$
现在我们设 $a'=ax,b'=by$，代入得：
$$
(a'+b')^k=\sum_{n=0}^{k} C^{n}_{k} a'^{k-n} b'^n
$$
我们将 $a'$ 和 $b'$ 变回原来的形式：
$$
(ax+by)^k=\sum_{n=0}^{k} C^{n}_{k} (ax)^{k-n} (by)^n
$$
我们就求出了多项式分解的公式。
## 思路
为了求解本题，我们需要对此公式拆解成每一项求解公式：
$$
a^nb^m=C^{m}_{k} x^{n}y^m a^{n}b^m\bmod10007
$$
系数即为 $C^{m}_{k} x^{n}y^m\bmod10007$。其中 $C^m_k=C^{m-1}_{k-1}+C^{m}_{k-1}$。
这道题就做出来了。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long //其实不用 long long 也能过。
using namespace std;
const int mod=1e4+7;
int poww(int x,int p){//快速幂
int result=1;
while(p>0){
if(p%2)result=result*x%mod;
p/=2;
x=x*x%mod;
}
return result;
}
int c[1005][1005];//这里的c[i][j]=c^i_j
signed main(){
int a,b,k,n,m;
cin>>a>>b>>k>>n>>m;
c[0][0]=1;
for(int i=1;i<=k;c[i][0]=c[i][i]=1,i++);
for(int i=1;i<=k;i++){
for(int j=1;j<i;j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//公式
}
}
cout<<c[k][n]*(poww(a,n)*poww(b,m)%mod)%mod<<endl;
return 0;
}
```
#### 后记
$\KaTeX$ 都快敲炸了，给个赞在走吧。