Codeforces Round #453 (Div. 2) D. GCD of Polynomials 数学构造

Codeforces Round #453 (Div. 2)

D. GCD of Polynomials

题意：定义 deg(A(x)) 为多项式 A(x) 的最高项的次数，要你构造两个多项式 A(x), B(x)，使得其可辗转相除恰好 n 次，即 { A(x), B(x) } -> { B(x), A(x)%B(x) } .........

tags：做不来这种构造题啊，，，但又确实是个好题，长见识了 *-*

很容易看出，要恰好 n 次，那 deg(A(x)) 肯定是 n， deg(B(x)) 肯定是 n-1。

然后类似 Fibonacci数列，{ f(n+1), f(n) }  ->   { f(n), f(n-1) }  ->  { f(n-1), f(n-2) } ......

递推式是 f(n+1) = x*f(n) + f(n-1)   %2 。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 200005;

int n, a[200][200];
int main()
{
    scanf("%d", &n);
    a[1][1]=1;
    a[2][1]=0, a[2][2]=1;
    rep(i,3,n+1)
    {
        rep(j,2,i)
            a[i][j] = a[i-1][j-1];
        rep(j,1,i)
            ( a[i][j] += a[i-2][j] ) %=2;
    }
    printf("%d
", n);
    rep(j,1,n+1)
        printf("%d%c", a[n+1][j], " 
"[j==n+1]);
    printf("%d
", n-1);
    rep(j,1,n)
        printf("%d ", a[n][j]);

    return 0;
}