GCD of Polynomials [Codeforces Round #453 B]

http://codeforces.com/contest/901/problem/B

多項式でユークリッドの互除法をやる。
ユークリッドの互除法の計算回数がN回となる2組の多項式を答えよ。
なお多項式の係数は-1,0,1のどれかにせよ。

答え方は、係数で答える。

3
1 2 3 4

であれば、3次多項式で係数が次数の小さい方から1,2,3,4なので、「4x^3+3x^2+2x + 1」を表す

解法

http://codeforces.com/contest/901/submission/33470559

逆算する形で作っていこう。
最終的に(1,0)で終わるとすると、これに到達する多項式は色々あるが(x,1)というのが考えられる。
ユークリッドの互除法では剰余を取るが、次数は減る必要があるので、(a,b)の親を(ax+b,a)とする。
これを順番につくっていく。
多項式の係数だけを持つ配列を更新していきながら、作っていく。
説明が難しいので、下のコードを見るのがいいだろう。
係数を-1,0,1に収めよということなので、axとbを足す時にmod2をとっているが、とっても大丈夫かどうかは未証明。
よく分からない。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<int> a = { 1 };
    vector<int> b = { 0 };

    rep(i, 0, N) {
        vector<int> c;

        // ax
        c.push_back(0);
        fore(j, a) c.push_back(j);

        // ax + b
        int M = b.size();
        rep(j, 0, M) c[j] = (c[j] + b[j]) % 2;

        swap(a, b); // b = a
        swap(a, c); // c = a
    }

    int n = a.size();
    printf("%d\n", n - 1);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%d", a[i]);
    } printf("\n");

    n = b.size();
    printf("%d\n", n - 1);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%d", b[i]);
    } printf("\n");
}