POJ 1060

Modular multiplication of polynomials

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 5093		Accepted: 2337

Description

Consider polynomials whose coefficients are 0 and 1. Addition of two polynomials is achieved by 'adding' the coefficients for the corresponding powers in the polynomials. The addition of coefficients is performed by addition modulo 2, i.e., (0 + 0) mod 2 = 0, (0 + 1) mod 2 = 1, (1 + 0) mod 2 = 1, and (1 + 1) mod 2 = 0. Hence, it is the same as the exclusive-or operation. 

(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2 

Subtraction of two polynomials is done similarly. Since subtraction of coefficients is performed by subtraction modulo 2 which is also the exclusive-or operation, subtraction of polynomials is identical to addition of polynomials. 

(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2 

Multiplication of two polynomials is done in the usual way (of course, addition of coefficients is performed by addition modulo 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 

Multiplication of two polynomials f(x) and g(x) modulo a polynomial h(x) is the remainder of f(x)g(x) divided by 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 
The largest exponent of a polynomial is called its degree. For example, the degree of x^7 + x^6 + 1 is 7. 

Given three polynomials f(x), g(x), and h(x), you are to write a program that computes f(x)g(x) modulo h(x). 
We assume that the degrees of both f(x) and g(x) are less than the degree of h(x). The degree of a polynomial is less than 1000. 

Since coefficients of a polynomial are 0 or 1, a polynomial can be represented by d+1 and a bit string of length d+1, where d is the degree of the polynomial and the bit string represents the coefficients of the polynomial. For example, x^7 + x^6 + 1 can be represented by 8 1 1 0 0 0 0 0 1.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of three lines that contain three polynomials f(x), g(x), and h(x), one per line. Each polynomial is represented as described above.

Output

The output should contain the polynomial f(x)g(x) modulo h(x), one per line.

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 

Source

Taejon 2001

大致题意：

给出三个多项式f、g、h,求(f*g)mod(h)，(最后一步mod，得到多项式除多项式的余数)。

定义两个多项式的加法和减法为当同幂级的项出现两次或不出现时，该幂级前边的系数为0，否则为1；两个多项式的乘法和普通的多项式乘法一样展开，然后按照加法或减法规则合并；两个多项式的除法为对这两个多项式相除取余。

解题思路：

定义两个多项式的加法和减法为当同幂级的项出现两次或不出现时，该幂级前边的系数为0，否则为1；

两个多项式的乘法和普通的多项式乘法一样展开，然后按照加法或减法规则合并；

两个多项式的除法为对这两个多项式相除取余。

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#define me(x) memset(x,0,sizeof(x))
int a[2009],b[2009],c[2009],d[2009];
int main()
{
    int n,len_a,len_b,len_c,len_d;
    scanf("%d",&n);
    while(n--)
    {
        me(a),me(b),me(c),me(d);
        scanf("%d",&len_a);
        for(int j=--len_a;j>=0;j--)      //这里是为了把幂和其位置相等，便于乘法计算。
        scanf("%d",&a[j]);
        
        scanf("%d",&len_b);
        for(int j=--len_b;j>=0;j--)
        scanf("%d",&b[j]);
        
        scanf("%d",&len_c);
        for(int j=--len_c;j>=0;j--)
        scanf("%d",&c[j]);
        
        for(int i=len_a;i>=0;i--)
        for(int j=len_b;j>=0;j--)
        {
           if(a[i]&&b[j]){             //多项式的乘法，这里还要用上那个他给定你的多项式运算的规则。
           if(d[i+j]) d[i+j]=0;
           else d[i+j]=1;
           }
        }
        len_d=len_a+len_b;      //d是a*b的答案。len_d也就是说这个答案的最高次幂是多少。
        while(len_d>=len_c)          //把d的最高次幂比c小。
        {
            int tmp;
            for(int i=len_c;i>=0;i--)   
                if(c[i]){
                if(d[len_d+i-len_c]) d[len_d+i-len_c]=0;
                else d[len_d+i-len_c]=1;
            }
            for(int i=len_d;i>=0;i--)   //找d的最高次幂。
                if(d[i]){
                len_d=i;
                break;
            }
        }
        printf("%d",len_d+1);
        for(int i=len_d;i>=0;i--)
        printf(" %d",d[i]);
        printf("\n");
    }
    return 0;
}