[蓝桥杯]序列计数

序列计数

题目描述

小明想知道，满足以下条件的正整数序列的数量：

1. 第一项为 nn；

2. 第二项不超过 nn；

3. 从第三项开始，每一项小于前两项的差的绝对值。

请计算，对于给定的 nn，有多少种满足条件的序列。

输入描述

输入一行包含一个整数 n(1≤n≤1000)n(1≤n≤1000)。

输出描述

输出一个整数，表示答案。答案可能很大，请输出答案除以 104104 的余数。

输入输出样例

示例

输入

4

输出

7

样例说明

以下是满足条件的序列：

4 1

4 1 1

4 1 2

4 2

4 2 1

4 3

4 4

运行限制

算法步骤

C++代码实现：

注意事项

测试点与优化建议

​​测试点​​	​​输入​​	​​预期输出​​	​​检查重点​​
最小值	n=1	1	边界条件
小规模	n=2	3	基础逻辑
中等规模	n=10	743	算法正确性
最大值	n=1000	xxxx	性能与溢出

​​优化建议​​：

• 最大运行时间：1s
• 最大运行内存: 256M

• 序列计数算法：动态规划 + 树状数组优化

• 算法思路

  该问题要求计算满足特定条件的序列数量，核心在于高效处理序列生成的约束条件。我们采用动态规划结合树状数组优化来解决：

• ​​状态定义​​：
  dp[i][j] 表示以 i 为第一项、j 为第二项的序列数量（包括长度为2及以上的合法序列）。

• ​​状态转移​​：
  对于状态 (i, j)：

  • 第三项 k 需满足 k < |i - j|
  • 转移方程：
    dp[i][j] = 1 + ∑ dp[j][k]（其中 k ∈ [1, |i-j|-1]）
  • 常数 1 表示序列 [i, j] 本身

• ​​优化策略​​：
  直接遍历 k 会导致 O(n^3) 复杂度。我们使用：

  • ​​树状数组​​：快速计算前缀和
  • ​​分组计算​​：按 max(i,j) 分组，保证依赖状态已计算

• ​​初始化​​：

  • 树状数组 trees[1..n]，每个维护长度为 n 的前缀和
  • dp 数组初始化为 0

• ​​分组计算​​（s 从 1 到 n）：

  for s = 1 to n:// 第一组：i = s, j ∈ [1, s]for j = 1 to s:d = |s - j|if d <= 1: dp[s][j] = 1else: dp[s][j] = 1 + trees[j].query(d-1)trees[s].update(j, dp[s][j])// 第二组：j = s, i ∈ [1, s-1]for i = 1 to s-1:d = |i - s|if d <= 1: dp[i][s] = 1else: dp[i][s] = 1 + trees[s].query(d-1)trees[i].update(s, dp[i][s])

• ​​结果计算​​：
  ans = ∑ dp[n][j]（j 从 1 到 n），结果模 10000

• #include <iostream>
  #include <vector>
  #include <cmath>
  using namespace std;const int MOD = 10000;// 树状数组类
  struct Fenw {int n;vector<int> c;Fenw(int size) : n(size), c(size + 1, 0) {}void update(int index, int delta) {while (index <= n) {c[index] = (c[index] + delta) % MOD;index += index & -index;}}int query(int index) {if (index <= 0) return 0;int sum = 0;while (index) {sum = (sum + c[index]) % MOD;index -= index & -index;}return sum;}
  };int main() {int n;cin >> n;// 初始化树状数组和dp数组vector<Fenw> trees;for (int i = 0; i <= n; i++) {trees.push_back(Fenw(n));}vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));// 动态规划计算for (int s = 1; s <= n; s++) {// 第一组：i = s, j ∈ [1, s]for (int j = 1; j <= s; j++) {int d = abs(s - j);if (d <= 1) {dp[s][j] = 1;} else {dp[s][j] = (1 + trees[j].query(d - 1)) % MOD;}trees[s].update(j, dp[s][j]);}// 第二组：j = s, i ∈ [1, s-1]for (int i = 1; i < s; i++) {int d = abs(i - s);if (d <= 1) {dp[i][s] = 1;} else {dp[i][s] = (1 + trees[s].query(d - 1)) % MOD;}trees[i].update(s, dp[i][s]);}}// 统计结果int ans = 0;for (int j = 1; j <= n; j++) {ans = (ans + dp[n][j]) % MOD;}cout << ans << endl;return 0;
  }

  实例验证（n=4）

• ​​计算过程​​：

  • dp[4][1] = 1 + trees[1].query(2) = 1 + 2 = 3
    （序列：[4,1], [4,1,1], [4,1,2]）
  • dp[4][2] = 1 + trees[2].query(1) = 1 + 1 = 2
    （序列：[4,2], [4,2,1]）
  • dp[4][3] = 1（序列：[4,3]）
  • dp[4][4] = 1（序列：[4,4]）
  • 总和：3 + 2 + 1 + 1 = 7

• ​​输出结果​​：

  输入：4
  输出：7

• ​​空间优化​​：

  • 树状数组空间 O(n^2)，n=1000 时约 2MB
  • 可改用滚动数组进一步优化

• ​​边界处理​​：

  • d-1=0 时跳过查询（树状数组下标从 1 开始）
  • abs(i-j)=0 时直接返回 1

• ​​时间复杂度​​：

  • 分组循环：O(n^2)
  • 树状数组操作：O(log n)
  • 总复杂度：O(n^2 log n)
• ​​记忆化搜索​​：
  改用递归 + 备忘录，避免冗余计算
• ​​并行计算​​：
  第二组 i 循环可并行执行
• ​​滚动数组​​：
  用一维数组代替 dp[i][j] 减少空间占用