Complete the Sequence

题目解析

这是一个非常经典的ACM/ICPC竞赛题目，通常被称为**“多项式插值”或“数列预测”**问题。

虽然题目提到了“多项式”和“最高次项D”，看起来像是一个需要求解方程组的代数题，但实际上，利用**差分表（Difference Table）**的性质来解决它是最简单、最稳健的方法。

核心数学原理：有限差分法

数学上有一个重要的定理：如果一个数列是由 $D$ 次多项式生成的，那么该数列的 $D$ 阶差分（即第 $D$ 层差值）是一个常数数列。 相应的， $D+1$ 阶差分全为 0。

举例说明

题目样例中的序列：1 2 4 7 11

第0层（原序列）: 1 2 4 7 11
第1层（相邻相减）: 1 2 3 4 (例如 2-1=1, 4-2=2…)
第2层（相邻相减）: 1 1 1

观察：第2层所有的数都相等（都是1）。这意味着这是一个 2次多项式 ( $D=2$ )。

如何预测下一个数？

既然第2层是常数，那么第2层的下一个数肯定还是 1。我们可以自底向上反推：

第2层下一个数是 1。
第1层下一个数 = 第1层当前最后一个数 4 + 第2层的新数 1 = 5。
第0层下一个数 = 第0层当前最后一个数 11 + 第1层的新数 5 = 16。

这就是我们解题的核心算法。

算法步骤详解

我们需要维护一个二维结构（或者递归结构）来模拟这个倒三角的差分表。

输入数据：读取 $S$ 个整数作为第 0 层数组。
向下构建差分表：
- 计算当前层的差分数组（后一项减前一项），作为下一层。
- 终止条件：如果当前层的所有数字都相等，或者当前层只剩下一个数字，则停止构建。
向后扩展（预测）：
- 既然最后一层是常数数列，我们在这一层的末尾追加 $C$ 个相同的数字。
向上回溯：
- 利用公式：上一层的下一个数 = 上一层原来的最后一个数 + 当前层刚算出的数。
- 一层层向上计算，直到算出第 0 层的新数值。
输出结果：第 0 层新追加的 $C$ 个数字即为答案。

图解演示

假设输入 1 2 4 7 11，预测 2 个数 ( $C=2$ )。

步骤 1：向下计算差分

Layer 0:  1   2   4   7   11
Layer 1:    1   2   3   4
Layer 2:      1   1   1      <-- 发现全相等，停止

步骤 2 & 3：向后扩展并向上回溯

我们要填补右边的空缺：

Plaintext

Layer 2:      1   1   1  [1]  [1]   (强行补常数)
                           |    |
           +---------------+    |
           v                    v
Layer 1:    1   2   3   4  [5]  [6]   (4+1=5, 5+1=6)
                           |    |
           +---------------+    |
           v                    v
Layer 0:  1   2   4   7   11 [16] [22]  (11+5=16, 16+6=22)

最终输出：16 22

C++ 代码实现

由于数据范围非常小 ( $S \le 100$ )，我们可以直接使用一个二维数组或 vector 数组来模拟这个过程，复杂度完全可以接受。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 检查这一层是否所有元素都相等
bool is_constant(const vector<int>& v) {
    if (v.empty()) return true; // 理论上不会空，防卫性编程
    for (size_t i = 1; i < v.size(); ++i) {
        if (v[i] != v[0]) return false;
    }
    return true;
}

void solve() {
    int S, C;
    if (!(cin >> S >> C)) return; // 读取失败处理

    vector<vector<int>> table;
    vector<int> first_row(S);
    
    // 1. 读取第一行输入
    for (int i = 0; i < S; ++i) {
        cin >> first_row[i];
    }
    table.push_back(first_row);

    // 2. 向下构建差分表
    int cur_layer = 0;
    while (true) {
        // 如果当前层只剩1个数，或者所有数都相等，则停止
        if (table[cur_layer].size() <= 1 || is_constant(table[cur_layer])) {
            break;
        }

        vector<int> next_row;
        for (size_t i = 0; i < table[cur_layer].size() - 1; ++i) {
            // 后一项减前一项
            next_row.push_back(table[cur_layer][i+1] - table[cur_layer][i]);
        }
        table.push_back(next_row);
        cur_layer++;
    }

    // 3. 填充后续的 C 个数字
    // 我们需要循环 C 次，每次为所有层增加一个数字
    for (int k = 0; k < C; ++k) {
        // 最底层直接复制它自己的最后一个元素
        // (因为最底层是常数，下一个数等于最后一个数)
        int last_val = table.back().back();
        table.back().push_back(last_val);

        // 从倒数第二层开始向上回溯
        for (int i = table.size() - 2; i >= 0; --i) {
            // 上一层的末尾 + 当前层的末尾 = 上一层的新末尾
            int new_val = table[i].back() + table[i+1].back();
            table[i].push_back(new_val);
        }
    }

    // 4. 输出第0层新增的 C 个数字
    // 原始长度是 S，新增的从下标 S 开始
    for (int i = 0; i < C; ++i) {
        cout << table[0][S + i] << (i == C - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

复杂度分析

空间复杂度：我们需要存储差分表。最坏情况下，差分表是一个大小为 $S \times S$ 的三角形。因为 $S \le 100$ ，空间大约是 $10000$ 个整数，非常小。
时间复杂度：
- 构建差分表：大约需要做 $S^2/2$ 次减法。
- 回溯预测：对于每个要预测的数，我们需要遍历所有层（最多 $S$ 层），共预测 $C$ 个数。操作次数约 $S \times C$ 。
- 总复杂度： $O(S^2 + S \times C)$ 。
- 考虑到 $T$ 组数据， $S, C \le 100$ ，总计算量在 $10^5$ 级别，远低于通常的 1秒 ( $10^8$ 次运算) 限制，可以瞬间完成。

特殊情况注意

S=1：如果只有一个数，比如输入 5，那么差分表第一层直接停止（只有一个数），判定为常数。输出就是 5 5 5 ...。代码中的 size() <= 1 判断处理了这种情况。
复杂多项式：题目样例 1 1 1 1 1 1 1 1 1 2，前面全是1，突然变2。这意味着这实际上是一个次数非常高的多项式（差分很多层之后才会出现非0变化）。这种方法天然支持这种情况，差分表会一直减下去直到只剩一个数为止。

总结

这道题不需要高斯消元，也不需要拉格朗日插值公式。利用差分表的递归性质（高阶等差数列性质）直接模拟，是编程实现最简单、且不容易出现浮点数精度误差的方法。

目录