Bài D - Codeforces Round #543 (Div.2)

Bài D:
Đề bài: Giả sử bạn có hai đa thức A(x)=a(0)x^0+a(1)x^1+...+a(n)x^n và B(x)=b(0)x^0+b(1)x^1+...+b(m)x^m. Đa thức A(x) có thể biểu diễn duy nhất dưới dạng sau A(x)=B(x)D(x)+R(x), deg R(x)<deg B(x).
Điều này có thể được thực hiện bằng cách sử dụng long division. Ở đây, deg P(x) kí hiệu là bậc của đa thức P(x). R(x) được gọi là dư của phép chia của đa thức A(x) cho B(x), và nó kí hiệu là A mod B.
 Bởi vì đây là một cách để chia đa thức với số dư, chúng ta có thể sử dụng thuật toán Euclide để tìm ước chung lớn nhất của hai đa thức. Thuật toán lấy hai đa thức (A,B). Nếu đa thức B(x) bằng 0, thì kết quả là A(x) và ngược lại kết quả của giá trị của thuật toán sẽ trả về cặp (B, A mod B). Cứ mỗi bước, bậc của đa thức 2 sẽ giảm xuống, vì vậy thuật toán làm việc hữu hạn lần. Nhưng số lượng đó lớn bao nhiêu? Bạn phải trả lời cho câu hỏi này.
 Bạn được cho một số nguyên n. Bạn phải xây dựng hai đa thức với bậc không vượt quá n, thỏa mãn rằng hệ số của chúng đều là số nguyên không vượt quá 1 bởi giá trị tuyệt đối của chúng, hệ số dẫn đầu (hệ số đi với số mũ lớn nhất của x) đều bằng 1, thuật toán Euclid được mô tả biểu diễn chính xác n bước tìm ước chung lớn nhất. Hơn thế nữa, bậc của đa thức đầu tiên phải lớn hơn bậc của đa thức thứ hai. Từng bước của thuật toán có nghĩa là từ cặp (A,B) đến cặp (B, A mod B)
Đầu vào:
 Bạn được cho số nguyên n (1<=n<=150) - số bước của thuật toán bạn cần đạt tới.
Đầu ra:
Hai đa thức dưới dạng sau:
+ Dòng đầu tiên chứa số nguyên m (0<=m<=n)- là bậc của đa thức.
+ Dòng thứ hai chứ m+1 số nguyên từ -1 đến 1 - là hệ số của đa thức, từ hằng số đầu tiên dẫn đầu.
+ Bậc của đa thức đầu tiên lớn hơn hoặc bằng bậc của đa thức thứ hai, hệ số dẫn đầu bằng 1. Thuật toán Euclide nên biểu diễn chính xác n bước khi gọi sử dụng đa thức này.
Nếu không có câu trả lời cho n, in ra -1
Nếu có nhiều đáp án, in ra đáp án bất kì.
Ví dụ:
Đầu vào:
1
Đầu ra:
1
0 1
0
1
/***/
Đầu vào:
2
Đầu ra:
2
-1 0 1
1
0  1
Chú ý:
Ở ví dụ thứ 2, bạn có thể in đa thức x^2-1 và x. Chuỗi này như sau: (x^2-1,x)->(x,-1)->(-1,0).
Có hai bước trong nó.
Hướng dẫn: Đối với số nguyên, chúng ta biết rằng trường hợp xấu nhất là dãy Fibonacci F(n+1)=F(n)+F(n-1). Giải pháp của vấn đề này là dựa trên ý tưởng trên. Có hai giải pháp được dự định. Đầu tiên bạn nên chú ý rằng: p(0)=1,p(1)=x, p(n+1)=x.p(n)+(-) p(n-1) cho ta một họ các giải pháp, chúng ta phải output p(n) và p(n-1). Nó có thể kiểm tra trực tiếp cho những hạn chế được cho mà bạn luôn chọn + hoặc - để thõa mãn hạn chế hằng số.
 Một giải pháp thứ hai là cùng với dãy trên nhưng bạn sử dụng dấu + thay vì +(-) và lấy hệ số module 2. Điều này cũng đúng vì nếu dãy những số dư có k bước trong khi bạn xét các số bởi cùng modulo nó sẽ có ít nhất k bước trong các số hợp lý. Vì vậy giải pháp thứ hai là: p(0)=1,p(1)=x,p(n+1)=x.p(n)+p(n-1) mod 2.
Lời giải:

#include<bits/stdc++.h>
using namespace std;
bitset<1000>a[1005];
int main()
{
    int n,i,j;
    cin>>n;
    a[1]=1;
    for(i=2;i<=n+1;i++)a[i]=(a[i-1]<<1)^a[i-2];
    cout<<n<<endl;
    for(i=0;i<=n;i++)cout<<a[n+1][i]<<' ';cout<<endl;
    cout<<n-1<<endl;
    for(i=0;i<=n-1;i++)cout<<a[n][i]<<' ';

    return 0;
}