POJ1060 HDU1343 ZOJ1026 UVALive2323 Modular multip

2019-04-14 20:34发布

站内文章 / 模拟电子
15408 0 1438
class="markdown_views prism-atelier-sulphurpool-light"> 这是《近世代数》的理论
其中有提到多项式模除2
计算如下：
这里写图片描述
多项式计算乘法：(模除2)
计算如下：
sum[i+j]=sum[i+j]^(f[i]&f[j])
sum的长度为f数组长度加g数组长度减1
即：lf+lg-1； #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef unsigned long long ULL; int compare(int a[],int la,int b[],int lb) { if(la>lb) return 1; else if(lareturn -1; else for(int i=la-1;i>=0;i--) { if(a[i]&&!b[i]) return 1; else if(b[i]&&!a[i]) return -1; } return 0; } const int N=1005; int main() { int f[N],g[N],h[N]; int sum[2*N]; int n,lf,lg,lh; scanf("%d",&n); while(n--) { scanf("%d",&lf); for(int i=lf-1;i>=0;i--) scanf("%d",&f[i]); scanf("%d",&lg); for(int i=lg-1;i>=0;i--) scanf("%d",&g[i]); scanf("%d",&lh); for(int i=lh-1;i>=0;i--) scanf("%d",&h[i]); memset(sum,0,sizeof(sum)); int ls=lf+lg-1; for(int i=0;ifor(int j=0;jwhile(compare(sum,ls,h,lh)>=0) { int d=ls-lh; for(int i=0;iwhile(ls&&!sum[ls-1]) ls--; } if(ls==0) ls=1; printf("%d ",ls); for(int i=ls-1;i>=0;i--) printf("%d ",sum[i]); printf(" "); } return 0; }

热门文章