[NOIP2011提高组day2]-1-计算系数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1．计算系数
(factor.cpp/c/pas)
【问题描述】
k n m
给定一个多项式(ax+by)^k ，请求出多项式展开后(x^n)*(y^m)项的系数。
【输入】
输入文件名为 factor.in。
共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取
模后的结果。

【输入输出样例】
factor.in
1 1 3 1 2
factor.out
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。

二项式系数：

是解决这道题的最直接方法；

很容易得出ans=a^n*b^m*c(k,m)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
using namespace std;
#define LL long long
#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)<(y)?(x):(y))
#define FILE "1"
const int maxn=,mod=;
int a,b,k,n,m;
int c[maxn][maxn];
namespace OI{
void init(){scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);}
int getc(int d){
if(d>k-d)d=k-d;
for(int i=;i<=k;i++){
c[i][]=;
for(int j=;j<=d&&j<=i;j++){
if(!c[i][i-j])c[i][j]=(c[i-][j]+c[i-][j-])%mod;
else c[i][j]=c[i][i-j];
} }
return c[k][d];
}
void slove(){
init();
a%=mod,b%=mod;
LL ans=;
up(i,,n)ans=ans*a%mod;
up(i,,m)ans=ans*b%mod;
ans=ans*getc(m)%mod;
cout<<ans<<endl;
}
}int main(){
using namespace OI;
slove();
}