
1计算系数
给定一个多项式 (ax + by)k ,请求出多项式展开后 x n y m 项的系数。
【输入】
输入文件名为 factor.in。
共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取 模后的结果。
【输入输出样例】
factor.in |
factor.out |
1 1 3 1 2 |
3 |
【数据范围】
对于 30%的数据,有 0≤k≤10; 对于 50%的数据,有 a = 1,b = 1;
对于 100%的数据,有 0≤k≤1,000,0≤n, m≤k,且 n + m = k,0≤a,b≤1,000,000。
【思路】
本题考查计算组合公式。可以知道答案就是C[k][m]*a^n*b^m。
有两种递归方式:
一种计算第n行,C[i]=C[i-1]*(k-i+1)/i 但实践得知这种递推的方式不能用模运算。
一种计算是把表全部递推出来 C[k][i]=C[k-1][i]+C[k-1][i-1];这种方法可以用模且时间足够。
【代码】
#include<iostream>
using namespace std;
const int MOD= ;
long long C[][];
int a,b,k,n,m;
int main() {
cin>>a>>b>>k>>n>>m;
for(int i=;i<=k;i++) {
C[i][]=;C[i][i]=;
for(int j=;j<=i-;j++) C[i][j]=(C[i-][j]+C[i-][j-])%MOD;
}
long long res=;
for(int i=;i<=n;i++) res=(res*a)%MOD; //a^n
for(int i=;i<=m;i++) res=(res*b)%MOD; //b^m
res=(res*C[k][m])%MOD;
cout<<res;
return ;
}