poj 1060 Modular multiplication of polynomialsバイナリ多項式取余式演算。

テーマ：由来はhttp://poj.org/problem?id=1060
説明:
              バイナリ多項式加算と減算を定義します。 ：  
                          (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)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

    ：

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)   け ：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;
}
  
  ： い、お が きます