解题思路

1. 问题理解：

   • 给定一个长度为$S$ 的整数序列 $X_1, X_2, \ldots, X_S$，需要找到一个最低次数的多项式 $P(n)$ 满足 $P(i) = X_i$（$1 \leq i \leq S$）。
   • 利用该多项式预测接下来的 $C$个值 $P(S+1), P(S+2), \ldots, P(S+C)$。

2. 多项式性质分析：

   • 任何有限序列都可以用多项式表示，关键在于找到最低次数的多项式。
   • 多项式次数 $d$ 可以通过差分法确定：计算序列的差分直到差分序列变为常数，此时差分次数即为 $d$。

3. 差分法应用：

   • 一阶差分：$\Delta_{1}X_i = X_{i+1} - X_i$
   • 二阶差分：$ \Delta_{2} X_i = \Delta_{1}X_{i+1} - \Delta_{1} X_i $
   • 重复计算直到 $\Delta_{d} X_i$ 为常数序列，此时 $d$ 为多项式次数。

代码实现

#include <iostream>
using namespace std;

typedef long long ll;
const int maxx = 110;
const int mod = 10007;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;

int a[maxx][maxx];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < maxx; i++) {
			for (int j = 0; j < maxx; j++) {
				a[i][j] = 0;
			}
		}
		
		int s, c;
		cin >> s >> c;
		
		for (int i = 0; i < s; i++)
			cin >> a[0][i];
		
		for (int i = 1; i < s; i++)
			for (int j = 0; j < s - i; j++)
				a[i][j] = a[i - 1][j + 1] - a[i - 1][j];
		
		for (int i = 1; i <= c; i++)
			a[s - 1][i] = a[s - 1][0];
		
		for (int i = s - 2; i >= 0; i--)
			for (int j = 0; j < c; j++)
				a[i][s - i + j] = a[i + 1][s - i + j - 1] + a[i][s - i + j - 1];
		
		for (int i = 0; i < c - 1; i++)
			cout << a[0][s + i] << " ";
		cout << a[0][s + c - 1] << "\n";
	}
	return 0;
}