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"); }