问题本质

构造波浪序列 $[a_1,a_2,...,a_m]$，满足：

• $a_1 = k$
• $\sum a_i = n$
• 相邻元素不等且增减交替

核心思路：动态规划

状态定义

dp[i][j][0/1] - 总和为 i，最后一个数为 j，最后一步是下降(0)/上升(1)的方案数

状态转移

• 从下降状态（下一步必须上升）： dp[i+j][j][1] += dp[i][x][0] 对所有 x > j

• 从上升状态（下一步必须下降）： dp[i+j][j][0] += dp[i][x][1] 对所有 x < j

关键优化

使用前缀和将转移复杂度从 $O(n)$ 降为 $O(1)$：

• 维护 prefix[i][j] = Σ dp[i][1..j][0]
• 维护 suffix[i][j] = Σ dp[i][j..n][1]

算法步骤

1. 初始化 dp[k][k][0] = dp[k][k][1] = 1
2. 按总和 i 从小到大计算 DP
3. 使用前缀和数组优化转移
4. 答案 = $\sum_{j=1}^n (dp[n][j][0] + dp[n][j][1])$

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

实现要点

• 模 $10^9+7$ 运算
• 注意单天计划 [k] 是合法序列
• 利用前缀和避免重复计算