Stupid Sequence

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

1 0 0 0 0 0 0
0 1 1 0 0 0 0
This is a smart sequence!

一道比较正常的水题

法一：高斯消元

高斯消元我就不多说了，可以看一眼这个题目 P3389

法二：线性代数

首先这样一张表

*	$x^0$	$x^1$	$x^2$	$x^3$	$x^4$	$x^5$	$x^6$
x=1	1	1	1	1	1	1	1
x=2	1	2	4	8	16	32	64
x=3	1	3	9	27	81	243	729
x=4	1	4	16	64	256	1024	4096
x=5	1	5	25	125	625	3125	15625
x=6	1	6	36	216	1296	7776	46656
x=7	1	7	49	343	2401	16807	117649

然后求其逆矩阵如下

	1	2	3	4	5	6	7
1	7	-21	35	-35	21	-7	1
2	-11.15	43.95	-79.08333333	82	-50.25	16.98333333	-2.45
3	7.088888889	-32.74166667	64.83333333	-70.69444444	44.66666667	-15.40833333	2.255555556
4	-2.3125	11.83333333	-25.39583333	29.33333333	-19.27083333	6.833333333	-1.020833333
5	0.409722222	-2.25	5.145833333	-6.277777778	4.3125	-1.583333333	0.243055556
6	-0.0375	0.216666667	-0.520833333	0.666666667	-0.479166667	0.183333333	-0.029166667
7	0.001388889	-0.008333333	0.020833333	-0.027777778	0.020833333	-0.008333333	0.001388889

由此我们就可以打表求解

得到一个粗制滥造的表，伪代码如下

const double poi[8][8] = {
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 7, -21, 35, -35, 21, -7, 1},
    {0, -11.15, 43.95, -79.08333333, 82, -50.25, 16.98333333, -2.45},
    {0, 7.088888889, -32.74166667, 64.83333333, -70.69444444, 44.66666667, -15.40833333, 2.255555556},
    {0, -2.3125, 11.83333333, -25.39583333, 29.33333333, -19.27083333, 6.833333333, -1.020833333},
    {0, 0.409722222, -2.25, 5.145833333, -6.277777778, 4.3125, -1.583333333, 0.243055556},
    {0, -0.0375, 0.216666667, -0.520833333, 0.666666667, -0.479166667, 0.183333333, -0.029166667},
    {0, 0.001388889, -0.008333333, 0.020833333, -0.027777778, 0.020833333, -0.008333333, 0.001388889},
};

因而在读取时将前 $7$ 个数据转为一个矩阵，求上矩阵与此矩阵的乘积既得 $a_0$~$a_6$ 的值

接下来变读取边验证即可

法三：最带劲的做法

观察题目可知 $a_0$~$a_6$ 均小于 $1000$，而每组数据都给了 $1500$ 个数

那么……

也就是说，在第 $1001$ 个数时，我们可以通过取模取得 $a_0$~$a_6$ 的值

剩下的就只有带入验证了

求解 $a_0$~$a_6$ 伪代码如下

for (int i = 0; i <= 6; i++) {
    ans[i] = s
    if (s < ans[i])
        break;
    s -= ans[i];
    s /= 1001;
}

带入验证时只要有一个数据不符合题意就可以弹出

伪代码如下

bool flag = 0;
for (int i = 1; i <= 1500; i++) {
    s = 0;
    for (int j = 6; j >= 0; j--) {
        s += ans[j];
        if (j)
            s *= i;
    }
    if (s != o[i]) {
        flag = 1;
        break;
    }
}

最后放一下完整代码

#include <cmath>
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
int T;
int main() {
    scanf("
    while (T--) {
        ll o[2000], s;
        for (int i = 1; i <= 1500; i++) {
            scanf("
        }
        s = o[1001];
        int ans[10];
        for (int i = 0; i <= 6; i++) {
            ans[i] = s
            if (s < ans[i])
                break;
            s -= ans[i];
            s /= 1001;
        }
        bool flag = 0;
        for (int i = 1; i <= 1500; i++) {
            s = 0;
            for (int j = 6; j >= 0; j--) {
                s += ans[j];
                if (j)
                    s *= i;
            }
            if (s != o[i]) {
                flag = 1;
                break;
            }
        }
        if (flag)
            printf("This is a smart sequence!\n");
        else {
            printf("
            for (int i = 1; i <= 6; i++) {
                printf("
            }
            printf("\n");
        }
    }
    return 0;
}