题目来源：http://poj.org/problem?id=1060
题目大意：
考虑系数为0和1的多项式。两个多项式的加法可以通过把相应次数项的系数相加而实现。但此处我们用模2加法来计算系数之和。一个实例：
(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
同样，多项式的减法我们在求系数之差时也用模2减法，例如：
(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
多项式的乘法与平常的做法一致，但同次项系数相加时使用模二加法，例如：
(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1
两个多项式f(x)和g(x)模多项式h(x)是求f(x)*g(x)除以h(x)的余数。例如：
(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) modulo (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1
多项式中最高次数称为degree。给出f(x) g(x)和h(x)，写一个程序求出 f(x)*g(x) mod h(x) 的结果。假定f(x)和g(x)的degree都小于h(x)，多项式的degree都小于1000。
由于系数都是0或1，假设多项式的degree为d，那么该多项式可以由一个次数指示整数(d + 1)和d+1个二进制位来表示。比如x^7 + x^6 + 1 可表示为： 8 1 1 0 0 0 0 0 1.
输入：由T个测试用例组成，并在输入的第一行给出T的值。每个用例由三行组成，分别为f(x)，g(x)，h(x)。多项式的表示方法如前所述。
输出：用如前所述的表示方式表达f(x)*g(x)%h(x)的值。每行对应一个输出的多项式。
Sample Input
2
7 1 0 1 0 1 1 1
8 1 0 0 0 0 0 1 1
9 1 0 0 0 1 1 0 1 1
10 1 1 0 1 0 0 1 0 0 1
12 1 1 0 1 0 0 1 1 0 0 1 0
15 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1
Sample Output
8 1 1 0 0 0 0 0 1
14 1 1 0 1 1 0 0 1 1 1 0 1 0 0
模拟题， 需要注意的两个地方：
1. 虽然题目中涉及的f(x) g(x) h(x)和输出的结果r(x)最高次都不会超过1000, 但中间结果f(x) * g(x)的最高次可能会超过1000，最大到2000.
2. 余数为0情况应输出0 0.
第一次用bitset.
////////////////////////////////////////////////////////////////
// POJ1060 Modular multiplication of polynomials
// Memory: 224K Time: 63MS
// Language: C++ Result : Accepted
/////////////////////////////////////////////////////////////// #include <iostream>
#include <bitset> using namespace std; bitset<> fx;
bitset<> gx;
bitset<> hx;
bitset<> rx;
int dfx, dgx, dhx, drx; int main(void) {
int T;
cin >> T;
for (int case_id = ; case_id < T; ++case_id) { fx.reset();
gx.reset();
hx.reset();
rx.reset(); //读取输入
cin >> dfx;
int buf;
for (int d = dfx - ; d >= ; --d) {
cin >> buf;
fx[d] = buf;
}
cin >> dgx;
for (int d = dgx - ; d >= ; --d) {
cin >> buf;
gx[d] = buf;
}
cin >> dhx;
for (int d = dhx - ; d >= ; --d) {
cin >> buf;
hx[d] = buf;
} //乘法计算
for (int d1 = dfx - ; d1 >= ; --d1) {
for (int d2 = dgx - ; d2 >= ; --d2) {
rx[d1 + d2] = fx[d1] & gx[d2] ^ rx[d1 + d2];
}
}
for (drx = ; drx >= ; --drx) {
if (rx[drx] == ) {
++drx;
break;
}
} //除法计算
while (drx >= dhx && drx > ) {
int t = drx - dhx;
for (int d = dhx - ; d >= ; --d) {
rx[d + t] = hx[d] ^ rx[d + t];
}
while (drx >= && rx[drx] == ) {
--drx;
}
++drx;
} //输出
cout << drx;
for (int d = drx - ; d > ; --d) {
cout << " " << rx[d];
}
cout << " " << rx[] << endl;
}
return ;
}
附测试数据：
input
output