1021: 多项式系数

Description

求 (ax+by)^k 的展开中 x^n*y^m 项的系数。由于系数可能很大，只要求输出除以 10007 的余数。

Input

一行共五个整数，分别为 a,b,k,n,m

Output

一个整数，为该项系数除以10007的余数。

Sample Input

1 1 3 1 2
Sample Output
3
HINT
数据范围：
30% 0<=k<=10,
50% a=1,b=1
100% 0<=k<=1000, 0<=n,m<=k 且 n+m=k, 0<=a,b<=100,000
NOIP2011 DAY2 factor
Source
NOIP2011
[Submit][Status]
#include<iostream>#include <cmath>#include "cstdio"/* 1、大数一般用10007取模 2、CKN=C(K-1)(N)+C(K-1)(N-1)//排列组合 3、利用以上公式递归处理，避免产生大数  */using namespace std;int a,b,k,n,m;int num[1001][1001];int test(int base,int number){    if(num[base][number]!=-1)        return num[base][number];        if(base==number||number==0){        num[base][number]=1;        return num[base][number];    }        num[base][number]=test(base-1,number)+test(base-1,number-1);    num[base][number]%=10007;    return num[base][number];}int main(){               //freopen("/Users/qigelaodadehongxiaodi/Desktop/data1.txt", "r", stdin);    //这个不理，是用来方便输入输出的东西，利用文本输入流来读取数据    //提交代码的时候记得注销这条语句        scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);;        for(int i=0;i<=k;i++)        for(int j=0;j<=k;j++)            num[i][j]=-1;        test(k,n);    num[k][n]%=10007;        for(int i=0;i<n;i++){        num[k][n]*=a%10007;        num[k][n]%=10007;    }        for(int i=0;i<m;i++){        num[k][n]*=b%10007;        num[k][n]%=10007;    }       PRintf("%d/n",num[k][n]%10007);         return 0;}