5434.[NOIP2011 提高组] 计算系数

算法思路

1. 问题分析

本题需要计算多项式 $(by+ax)^k$ 展开式中 $x^nym$ 项的系数。核心要点：

• 多项式展开符合二项式定理：$(by+ax)^k = \sum_{i=0}^{k} C_k^i (ax)^i (by)^{k-i}$
• 目标项 $x^nym$ 需满足 $n+m=k$（题目保证条件成立）
• 目标项系数为 $C_k^n a^n b^m$（或等价形式 $C_k^m a^n b^m$）

2. 解决策略

采用动态规划模拟多项式展开过程：

• 状态定义：dp[i][j] 表示 $(by+ax)^{i-1}$ 展开式中 $y^{j-1}$ 的系数
• 初始化：dp[1][1]=1（对应零次幂常数项）
• 状态转移：
  • 每个新系数由上一层的两个相邻系数加权得到
  • 递推式：dp[i][j] = (dp[i-1][j-1]*b + dp[i-1][j]*a) % mod
• 目标定位：dp[k+1][m+1] 对应 $x^nym$ 的系数

3. 复杂度分析

• 时间复杂度：$O(k^2)$
  双重循环遍历 $(k+1) \times (k+1)$ 的状态空间
• 空间复杂度：$O(k^2)$
  DP数组存储二维状态

---

代码实现

C++解法

cpp
复制
1#include <iostream>
2using namespace std;
3const int MOD = 10007;
4
5int main() {
6    long long a, b, k, n, m;
7    cin >> a >> b >> k >> n >> m;
8    
9    // DP数组：dp[i][j]表示(by+ax)<sup>{i-1}展开式中y</sup>{j-1}项的系数
10    long long dp[1010][1010] = {0};
11    dp[1][1] = 1;  // 初始状态：0次幂的常数项为1
12
13    // 动态规划递推：i为当前多项式次数+1
14    for (int i = 2; i <= k + 1; i++) {
15        // 计算(by+ax)^{i-1}展开式的j项系数（j从1到i）
16        for (int j = 1; j <= i; j++) {
17            // 状态转移：由i-1层的j-1项乘b（增加y的幂）和j项乘a（增加x的幂）
18            long long term1 = (j - 1 >= 1) ? dp[i - 1][j - 1] * b : 0; // O(1)操作
19            long long term2 = (j <= i - 1) ? dp[i - 1][j] * a : 0;      // O(1)操作
20            dp[i][j] = (term1 + term2) % MOD;  // 合并结果并取模
21        }
22    }
23    
24    cout << dp[k + 1][m + 1];  // 输出y<sup>m项系数（即x</sup>n*y^m项）
25    return 0;
26}

代码解释：

1. 参数说明：
   • a, b：多项式系数
   • k：多项式幂次
   • n, m：目标项的指数（满足 $n+m=k$）
2. 核心逻辑：
   • 初始化：dp[1][1]=1 表示零次幂常数项
   • 双层循环：
     • 外层 i 从2到k+1，对应多项式次数从1到k
     • 内层 j 计算当前幂次各项系数
   • 状态转移：
     • term1：继承自 $y^{j-2}$ 项并乘 $b$（增加 $y$ 指数）
     • term2：继承自 $y^{j-1}$ 项并乘 $a$（增加 $x$ 指数）
3. 边界处理：
   • 利用三元运算符处理越界情况（返回0）
   • 所有运算对10007取模防溢出

Python3解法

python
复制
1MOD = 10007
2
3def main():
4    a, b, k, n, m = map(int, input().split())
5    
6    # 初始化DP数组：dp[i][j]表示(by+ax)<sup>{i-1}中y</sup>{j-1}项系数
7    dp = [[0] * 1010 for _ in range(1010)]  # O(k^2)空间
8    dp[1][1] = 1  # 0次幂的常数项
9    
10    # 动态规划递推
11    for i in range(2, k + 2):    # i: 2~k+1 (对应多项式次数1~k)
12        for j in range(1, i + 1):  # j: 1~i (当前层项数)
13            # 状态转移（自动处理越界索引返回0）
14            term1 = dp[i - 1][j - 1] * b if j - 1 >= 1 else 0
15            term2 = dp[i - 1][j] * a if j <= i - 1 else 0
16            dp[i][j] = (term1 + term2) % MOD  # 取模防止溢出
17    
18    print(dp[k + 1][m + 1])  # 输出y^m项系数
19
20if __name__ == "__main__":
21    main()

代码解释：

1. 与C++差异：
   • Python利用嵌套列表实现二维数组
   • 边界检查通过条件表达式完成（避免显式越界）
2. Python特性：
   • 动态类型：无需声明变量类型
   • 列表推导：快速初始化二维数组
   • 条件表达式：简化边界处理逻辑
3. 关键语句：
   • dp = [[0]*1010 for _ in range(1010)]：创建1009×1009的二维数组（下标1开始）
   • if j-1>=1 else 0：安全访问前一层的左上方元素

---

复杂度对比

选择建议：

1. 竞赛场景：
   • 优先选择C++：处理 $k=1000$ 时效率更高（约快3-5倍）
   • 适用于对时限要求严格的比赛（如OI/ACM）
2. 快速开发：
   • 选择Python：代码更简洁，减少开发时间
   • 适用于数据规模较小（$k \leq 500$）或原型验证
3. 内存优化：
   • 双语言均可通过滚动数组优化空间至 $O(k)$
   • 递推式：dp[j] = (prev[j-1]*b + prev[j]*a) % MOD