计算系数 Editional

原题链接：https://ac.nowcoder.com/acm/problem/16596

题目描述：
给定一个多项式(ax+by)k，请求出多项式展开后xnym项的系数。
输入描述:
共一行，包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。
输出描述:
输出共1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。
示例1
输入
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。

记忆化的必要性
易得本题公式：ans = C(k,n) a^n b^m
若我们维护杨辉三角，就有O(k^2)的时空复杂度。
这样太慢了。
我们进一步观察可得：
ans = a^n b^m k! / (k-n)! / n!
在模10007的意义下，我们可以计算逆元。
时空复杂度降到O(k)。

#include<cstdio>
#include<cstring>
using namespace std;
#define mod 10007
int rec[1010][1010];    //使用递归组合数必须配个记忆化 ，不加卡成dog
int a,b,k,n,m;
inline int in(){
    int x=0;char ch=getchar();
    while(ch>'9' || ch<'0')    ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int C(int n,int r){
        if(n==r || r==0)    return rec[n][r]=1;
        if(rec[n][r])    return rec[n][r];
        return rec[n][r]=(C(n-1,r)+C(n-1,r-1))%mod;
    }
    long long power(long long x,int k){    //10006*10006是可能爆 int的 
    long long ans=1;
    while(k){
        if(k&1)    ans=ans*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return ans;
}
int main(){
    a=in();b=in();k=in();n=in();m=in();
    int ans=power(a,n)*power(b,m)%mod*C(k,m)%mod;
    printf("%d",ans);
    return 0;
}