首页 > ACM题库 > HDU-杭电 > Hdu 1343 Modular multiplication of polynomials-二项式[解题报告] C++
2013
12-09

Hdu 1343 Modular multiplication of polynomials-二项式[解题报告] C++

Modular multiplication of polynomials

问题描述 :

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.

(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2

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.

(x6 + x4 + x2 + x + 1) – (x7 + x + 1) = x7 + x6 + x4 + x2

Multiplication of two polynomials is done in the usual way (of course, addition of coefficients is performed by addition modulo 2).

(x6 + x4 + x2 + x + 1) (x7 + x + 1)
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 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).

(x6 + x4 + x2 + x + 1) (x7 + x + 1) modulo (x8 + x4 + x3 + x + 1)
= x7 + x6 + 1

The largest exponent of a polynomial is called its degree. For example, the degree of x7 + x6 + 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, x7 + x6 + 1 can be represented by

8 1 1 0 0 0 0 0 1.

输入:

The input consists of T test cases. The number of test cases (T) is given in the first line of the input. 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.

输出:

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

样例输入:

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

样例输出:

8 1 1 0 0 0 0 0 1 
14 1 1 0 1 1 0 0 1 1 1 0 1 0 0

描述:

定义二进制多项式加法和减法 :

(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^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

定义二进制多项式求余数;

(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

要求:输入g(x)、f(x)和h(x) 求出(g(x)*f(x))mod h(x)

具体输入要求如下:

2    (2个测试样例)
7 1 0 1 0 1 1 1   (g(x)     7表示多项式最大为x^6依次往下推)
8 1 0 0 0 0 0 1 1 (f(x) 8表示多项式最大为x^7依次往下推)
9 1 0 0 0 1 1 0 1 1 (h(x) 9表示多项式最大为x^8依次往下推)  这是第一测试样例,即每个测试样例占三行
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

思路:

        (1)  乘法:定义一个bitwap,做乘法的时候,先输入g(x),然后输入f(x)。每当f(x)第n位不等于0,就将g(x)移动n位即在bitmap上从n位开始,将g(x)加到bitmap上。

(2) 除法:每次都让h(x)与bitmap上的最高位len到len-len(h)+1与,相当于乘了x^n,将h(x)的最高位系数乘到乘积的最高位,然后求出余数比较余数的最高位与h(x)的最高位谁大,如果余数的最高位小于h(x)的最高位,则结束。

#include <iostream>
#include<cstdlib>

using namespace std;

#define  bitmapLen 2000
bool bitmap[bitmapLen];
bool Fx[1000];
bool Hx[1000];

class Modular{
public:
	Modular(int n){
		this->n = n;
	}
	void solution()
	{
		int i,j,k;
		for(i=0;i<n;i++){
			for(j=0;j<bitmapLen;j++){
				bitmap[j] = false;
			}

			int len1;
			cin>>len1;
			for(j=0;j<len1;j++){//输入g(x)
				int bit1;cin>>bit1;
				Fx[len1 - j-1] = (bool)bit1;
			}

			int len2;
			cin>>len2;
			int count = len2-1;
			for(j=0;j<len2;j++){//求乘积
				int bit2;cin>>bit2;//输入h(x),同时求乘积
				if(bit2){
					for(k=0;k<len1;k++)
						bitmap[k+count] ^= Fx[k]; 
				}
                count--;
			}

			int len = len1+len2-2;

            int len3;cin>>len3;
			for(j=0;j<len3;j++){//输入h(x)
				int bit3;cin>>bit3;
                Hx[len3 - j-1] = (bool)bit3;
			}
            len3--;
			while(len3<=len){
				j = len3;
				for(k=len;k>=len-len3;k--){//取商求余
					bitmap[k] ^= Hx[j--];
				}

				while(bitmap[len]==0)len--;//得到余数的最高位
			}
			cout<<len+1<<" ";
			for(k = len;k>=0;k--)cout<<bitmap[k]<<" ";
			cout<<endl;

		}
	}
protected:

private:
    int n;
};

int main()
{
	int n;
	cin>>n;
	Modular poj1060(n);
	poj1060.solution();
	system("pause");
	return 0;
}

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”