【题目来源】
洛谷：P1313 [NOIP 2011 提高组] 计算系数 - 洛谷
【题目描述】
给定一个多项式 \((by+ax)^k\)，请求出多项式展开后 \(x^n\times y^m\) 项的系数。
【输入】
输入共一行，包含 \(5\) 个整数，分别为 \(a,b,k,n,m\)，每两个整数之间用一个空格隔开。
【输出】
输出共一行，包含一个整数，表示所求的系数。
这个系数可能很大，输出对 \(10007\) 取模后的结果。
【输入样例】
1 1 3 1 2
【输出样例】
3
【算法标签】
《洛谷 P1313 计算系数》 #数学# #NOIP提高组# #2011#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型防止溢出
const int N = 1005; // 定义最大数组长度
const int mod = 10007; // 模数int a, b, k, n, m; // 输入参数
int f[N][N]; // 动态规划数组// f[i][j] 表示在(a+b)^i展开式中，x^n的指数为j的系数
// 注意：这里n是x的指数，j是当前x的指数signed main()
{// 输入参数：a, b, k, n, m// (a+b)^k 展开式中 x^n * y^m 的系数，其中 n+m=kcin >> a >> b >> k >> n >> m;// 初始化：k=1的情况// (a+b)^1 = a + bf[1][0] = b % mod; // 对应b，x的指数为0f[1][1] = a % mod; // 对应a，x的指数为1// 动态规划：计算(a+b)^i的展开式系数for (int i = 2; i <= k; i++){// 处理x指数为0的情况：只有b的贡献// (a+b)^i中x^0的系数 = (a+b)^(i-1)中x^0的系数 × bf[i][0] = f[i - 1][0] * b;f[i][0] %= mod;// 处理x指数从1到i的情况for (int j = 1; j <= i; j++){// 递推公式：// f[i][j] = f[i-1][j] * b + f[i-1][j-1] * a// 解释：// 1. 从(a+b)^(i-1)中x^j的系数乘以b得到x^j项// 2. 从(a+b)^(i-1)中x^(j-1)的系数乘以a得到x^j项f[i][j] = (f[i - 1][j] * b) + (f[i - 1][j - 1] * a);f[i][j] %= mod; // 取模防止溢出}}// 输出结果：x^n的系数（即x^n * y^m的系数）cout << f[k][n] << endl;return 0;
}
【运行结果】
1 1 3 1 2
2