[Noip2011]计算系数

问题 A: [Noip2011]计算系数
时间限制: 1 Sec 内存限制: 128 MB
题目描述
给定一个多项式(ax + by)k，请求出多项式展开后 x^n*y^m 项的系数。
输入
共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。
有0≤k≤1,000，0≤n,m≤k，且 n+m=k，0≤a,b≤1,000,000
输出
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取模后的结果。
样例输入
1 1 3 1 2
样例输出
3

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<queue>
#define LL long long 
using namespace std;
int p=10007;
inline int qpow(int m,int n)
{int ans=1;
 for(;n;n>>=1,m=m*m%p)
 if(n&1)
 ans=ans*m%p;
 return ans; 
}
LL cs[1005][1005];
LL ss(int a,int b)//组合数
{if(cs[a][b]!=-1)
 return cs[a][b];if(b==0){cs[a][0]=1;return 1;}  if(a==b){
 cs[a][a]=1;
 return 1; }cs[a][b]=ss(a-1,b)+ss(a-1,b-1);return cs[a][b]%p;
}
int main()
{
 memset(cs,-1,sizeof(cs));
 int a,b,k,n,m;
 int u=10007;
 scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
 a%=u;b%=u;
 LL as=qpow(a,n)%p,bs=qpow(b,m)%p;
 LL s=ss(k,m)%p;s*=as;s%=p;s*=bs;s%=p;
 printf("%lld",s);
 //while(1);
 return 0;
}