1026 Modular multiplication of polynomials

这道题目是多项式相乘、求模。。按照题目中的规则，可以看出，多项式的加法和减法是相同的结果，那么多项式的除法都可以用加法来计算了。代码的重点是21到24行，36到37行，是如何实现乘和求余的步骤。

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 #define MAXN 2000
 5 struct poly{ int deg,x[MAXN];};
 6  void print(poly f)
 7 {
 8        cout<<f.deg<<' ';
 9        for (int i=f.deg-1; i>0; --i) cout<<f.x[i]<<' ';
10        cout<<f.x[0]<<endl;
11 }
12  void read(poly &f)
13 {
14        cin>>f.deg;
15        for (int i=f.deg-1; i>=0; --i) cin>>f.x[i];
16 }
17 //r=f*g
18 void mult(poly f,poly g,poly &r)
19 {
20        memset(r.x,0,sizeof(r.x));
21        for (int i=0; i<f.deg; ++i)
22               for (int j=0; j<g.deg; ++j)
23                      r.x[i+j] = (r.x[i+j]+f.x[i]*g.x[j])%2;
24        r.deg = f.deg+g.deg-1;
25 }
26 //m=m%h
27 void mod(poly &m,poly h)
28 {
29        int i;
30        while (1){
31               for (i=m.deg-1; i>=0&&(!m.x[i]); --i);
32               if (i<h.deg-1){
33                      m.deg = i+1;
34                      break;
35               }
36               for (int j=h.deg-1; j>=0; --i,--j)
37                     m.x[i] = (m.x[i]+h.x[j])%2;
38        }
39 }
40 void solve()
41 {
42        poly f,g,h,m;
43        read(f);
44        read(g);
45        read(h);
46        mult(f,g,m);
47        mod(m,h);
48        print(m);
49 }
50 int main()
51 {
52        int t;
53        cin>>t;
54              while (t--)
55              solve();
56       return 0;
57 }