SPOJ - POLYNOM Polynomial（数论乱搞）题解

题意：给你n个数，问你是否存在一个多项式（最多三次方）满足f（i）= xi。

思路：讲一个神奇的思路：

x³- (x - 1)³ = 3x² - 3x + 1

x² - (x - 1)² = 2x + 1

x - (x - 1) = 1

1 - 1 = 0

看了上面这么多，其实已经可以发现一件事情了：如果相邻常数减一次那么就是0；相邻一次式减一次降为常数，减两次为0；相邻二次式减一次降为一次式，减两次降为常数，减三次....

由此我们可以知道，如果存在一个多项式（最多三次方）满足f（i）= xi，那么我相邻的数相减4次必为0，如果不满足，那肯定不是同个式子里的

代码：

#include<cstdio>

#include<set>

#include<vector>

#include<cmath>

#include<queue>

#include<cstring>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const double INF = 0x3f3f3f3f;

const ll MOD = ;

ll num[maxn];

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        ll n;

        scanf("%lld", &n);

        for(int i = ; i <= n; i++)

            scanf("%lld", &num[i]);

        for(int i = ; i <= ; i++){

            for(int j = n ;j > i; j--)

                num[j] = num[j] - num[j - ];

        }

        bool flag = true;

        for(int i = ; i <= n; i++){

            if(num[i]){

                flag = false;

                break;

            }

        }

        if(flag) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

/*

Input:

3

1 3

5 0 1 2 3 4

5 0 1 2 4 5

Output:

YES

YES

NO

*/

巴特西

SPOJ - POLYNOM Polynomial（数论乱搞）题解

最新文章

热门文章