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", n); rep(j,1,n+1) printf("%d%c", a[n+1][j], " \n"[j==n+1]); printf("%d\n", n-1); rep(j,1,n) printf("%d ", a[n][j]); return 0; }