EOJ2999-计算多项式的系数（递归）

题目

给定一个多项式

计算多项式展开后以下项的系数

输入

第 1 行：一个整数 T （1≤T≤100000）为问题数。
接下来共 T 行。每行 5 个整数，分别为 a，b，k，n，m，整数之间由一个空格分隔。0≤k≤1,000,000，0≤n,m≤k，且 n+m=k，0≤a,b≤10^9。

输出

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等）。
然后对应每个问题在一行中输出一个整数，表示所求的系数（这个系数可能很大，输出对 10007 取模后的值）。

思路

代码

#include <iostream>
#include <algorithm>
int mo = 10007;
long long int dp[1001][1001];
using namespace std;

long long int pow(int a, int b) {
    long long int result = 1;
    while (b--)
        result = (result * a) % mo;
        //一定要每乘一次取模一次，否则结果是错误的
    return result;
}

int main() {
    int turn;
    int a,b,k,n,m;
    cin >> turn;
    dp[0][0] = 1;
    
    for (int i = 0; i < turn; i++) {
        cin >> a >> b >> k >> n >> m;
        
        //先初始化数组
        for (int j = 1; j <= n; j++)
            dp[j][0] = pow(a, j) ;
        for (int j = 1; j <= m; j++)
            dp[0][j] = pow(b, j) ;

        //填充数组
        for (int ni = 1; ni <= n; ni++) 
            for (int mi = 1; mi <= m; mi++) 
                dp[ni][mi] = (a * dp[ni - 1][mi] + b * dp[ni][mi - 1]) % mo;
            
        cout << "case #" << i << ":" << endl;
        cout << dp[n][m] << endl;
    }
    
    return 0;
}