| NOIP201108计算系数 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
给定一个多项式(ax + by)^k，请求出多项式展开后(x^n)*(y^m)项的系数。 |
|
输入
|
|
共一行，包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。
|
|
输出
|
|
输出共1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。
|
|
输入示例
|
|
1 1 3 1 2
|
|
输出示例
|
|
3
|
|
其他说明
|
|
【数据范围】0≤k≤1,000，0≤n, m≤k，且n+m=k，0≤a，b≤1,000,000。
|
题解：先胡搞出答案是：C(n,n+m) * a^n * b^m
然后呢，指数部分用快速幂，C用逆元搞。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int mod=;
void exgcd(int a,int b,int&x,int&y){
if(!b){x=;y=;return;}exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return;
}
int pow(int x,int y){
int ans=;x%=mod;for(int i=y;i;i>>=,x=x*x%mod)if(i&)ans=ans*x%mod;return ans;
}
int ine(int t){
int x,y;exgcd(t,mod,x,y);x%=mod;if(x<=)x+=mod;return x;
}
int C(int n,int m){
int s1=,s2=;if(m>n-m)m=n-m;
for(int i=;i<=m;i++){
s1=s1*(n-i+)%mod;
s2=s2*i%mod;
}return s1*ine(s2)%mod;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
int a,b,k,n,m;
void init(){
a=read();b=read();k=read();n=read();m=read();
write(C(k,n)%mod*pow(a,n)%mod*pow(b,m)%mod);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}