poj 1060 Modular multiplication of polynomials 除数是大数的

题意：

给f(x),g(x),h(x)，求(f(x)*g(x))%h(x)。

分析：

难点是如何做除数是大数的高精度除法，如果除数不是大数只有被除数是大数的话4,5行代码就可以写除法部分了（http://blog.csdn.net/sepnine/article/details/46562599）。

代码：

//poj 1060
//sep9
#include <iostream>
using namespace std;
const int maxN=1024;
struct H
{
	int len;
	int a[2*maxN];	
	void scan(){
		scanf("%d",&len);
		for(int i=0;i<len;++i)
			scanf("%d",&a[len-1-i]);
	}
	void print(){
		printf("%d ",len);
		for(int i=0;i<len;++i)
			printf("%d ",a[len-1-i]);
		puts("");
	}
	H operator *(const H y)const{
		H t;
		t.len=len+y.len;
		for(int i=0;i<t.len;++i)
			t.a[i]=0;
		for(int i=0;i<len;++i)
			for(int j=0;j<y.len;++j)
				t.a[i+j]+=a[i]*y.a[j];
		for(int i=0;i<t.len;++i)
			t.a[i]%=2;
		while(t.len>0&&!t.a[t.len-1])
			--t.len;
		return t;
	}
	H operator +(const H y)const{
		H t;
		t.len=max(len,y.len);
		int i=0;
		while(i<len&&i<y.len){
			t.a[i]=a[i]^y.a[i];
			++i;
		}
		while(i<len){
			t.a[i]=a[i];
			++i;
		}
		while(i<y.len){
			t.a[i]=y.a[i];
			++i;
		}
		while(t.len>0&&!t.a[t.len-1])
			--t.len;
		return t;			
	}
	H operator %(const H y)const{
		H mod,q,two;
		two.len=2,two.a[0]=0,two.a[1]=1;
		q.len=len;
		mod.len=0;
		for(int i=len-1;i>=0;--i){
			mod=mod*two;
			mod.a[0]=a[i];
			if(mod.len==0)
				++mod.len; 
			if(mod.len<y.len)
				q.a[i]=0;
			else{
				q.a[i]=1;
				for(int j=0;j<mod.len;++j)
					mod.a[j]=mod.a[j]^y.a[j];
				while(mod.len>0&&!mod.a[mod.len-1])
					--mod.len;
			}		
		}	
		return mod;
	}
};
H f,g,h,tmp;

int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		f.scan();
		g.scan();
		h.scan();
		((f*g)%h).print();
	}
	return 0;	
}