UVa 1546 - Complete the sequence!

#数学 #差分序列

Published on 2016-03-15

描述

给定 $S(1\le S < 100)$ , $C(1 \le C < 100)$ 以及 $f(1), f(2),...,f(S)$ ，请你根据 $S$ 个函数值，求出一个最高次项最小的通项公式，并输出 $f(S + 1), f(S + 2),...,f(S + C)$ 的值。输入保证存在最高次数不超过 $S - 1$ 的通项公式。

样例输入

4
6 3
1 2 3 4 5 6
8 2
1 2 4 7 11 16 22 29
10 2
1 1 1 1 1 1 1 1 1 2
1 10
3

样例输出

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3

分析

老实说，给定前几项，我可以求出无数个通项公式，比如 $1, 4, 9, 16$ ，看起来有 $f(n) = n^2$ 。事实上我可以令 $f(n) = (n - 1)(n - 2)(n - 3)(n - 4) + n^2$ ，这也是对的，可以无限制的构造，所以我们要求的是最小的通项公式。
当然可以枚举最高次项，使用高斯消元求出通项公式，可那麻烦了，我们介绍差分序列：
如果原序列是 $1, 4, 9, 16...$ ，那么它的一次差分序列就是 $3, 5, 7$ ，原序列两个数之间的差。二次差分序列就是 $2, 2$ ，三次差分序列是 $0$ 。
观察发现，如果最高次是 $n$ 次，那么将在 $n + 1$ 次差分后达到 $0$ ，需要 $n + 1$ 个函数值，这也就是为什么题目保证存在最高次数不超过 $S - 1$ 的通项公式的原因。
既然已经知道一定会走向 0，那么把差分序列写成下三角型，递推一下很容易搞定后面的值。

代码

//  Created by Sengxian on 3/15/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 1546 差分序列
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100 + 3;
int n, m, a[maxn][maxn];

int main() {
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt(), m = ReadInt();
        memset(a, 0, sizeof a);
        for (int i = 0; i < n; ++i)
            a[0][i] = ReadInt();
        for (int i = 1; i < n; ++i)
            for(int j = 0; j < n - i; ++j)
                a[i][j] = a[i - 1][j + 1] - a[i - 1][j];
        a[n][0] = 0;
        for(int j = 0; j < m; ++j)
            for(int i = n - 1; i >= 0; --i)
                a[i][j + n - i] = a[i][j + n - i - 1] + a[i + 1][j + n - i - 1];
        for(int i = 0; i < m; ++i)
            printf("%d%c", a[0][n + i], i + 1 == m ? '\n' : ' ');
    }
    return 0;
}

高斯消元法造 BestCoder Round #75 之记

Sengxian's Blog