POJ 1060 - Modular multiplication of polynomials

http://poj.org/problem?id=1060

概要

多項式 \(f(x), g(x), h(x)\) が与えられる． 係数の演算は modulo 2 で行う． このとき，\(f(x) \cdot g(x) \mbox{ modulo } h(x)\) の係数を答える．

制約

• 多項式の次数は最大で 1000

解法

実際に \(f(x) \cdot g(x)\) を計算して \(h(x)\) で割って余りを求める． 係数の計算は xor なので，bitset を使うと実装が楽．

 1 #include <cstdio>
 2 #include <bitset>
 3 using namespace std;
 4 static const int N = 2000;
 5 
 6 pair<int, bitset<N+N> > read()
 7 {
 8   int n;
 9   scanf("%d", &n);
10   bitset<N+N> f;
11   for (int i = 0; i < n; i++) {
12     int x;
13     scanf("%d", &x);
14     f.set(n-i-1, x);
15   }
16   return make_pair(n, f);
17 }
18 
19 int main()
20 {
21   int T;
22   scanf("%d", &T);
23   while (T-- > 0) {
24     pair<int, bitset<N+N> > f, g, h;
25     f = read();
26     g = read();
27     h = read();
28     bitset<N+N> fg;
29     for (int i = 0; i < N; i++) {
30       if (f.second.test(i)) {
31         fg ^= g.second;
32       }
33       g.second <<= 1;
34     }
35     const int M = h.first-1;
36     h.second <<= (N-M);
37     bitset<N+N> a;
38     for (int i = N-M; i >= 0; i--) {
39       if (fg.test(i+M)) {
40         a.set(i);
41         fg ^= h.second;
42       }
43       h.second >>= 1;
44     }
45     int i;
46     for (i = N-1; !fg.test(i); i--);
47     printf("%d", i+1);
48     for (; i >= 0; i--) {
49       printf(" %d", fg.test(i));
50     }
51     putchar('\n');
52   }
53   return 0;
54 }