做不锈钢门的网站/客服外包平台

考虑系数为0和1的多项式。两个多项式的加法是通过在多项式中添加相应幂的系数来实现的。系数的增加是通过增加模2来实现的，即， (0 + 0) mod 2 = 0， (0 + 1) mod 2 = 1， (1 + 0) mod 2 = 1， (1 + 1) mod 2 = 0。因此，它与排除或操作是相同的。
(x x ^ ^ 6 + 4 + x ^ 2 + x + 1)+(x ^ 7 + x + 1)= x ^ 7 + x ^ 6 + x ^ 4 + x ^ 2
两个多项式的减法也是类似的。由于系数的减法是通过减法模2进行的，它也是排除法或运算，所以多项式的减法和多项式的加法是一样的。
(x x ^ ^ 6 + 4 + x ^ 2 + x + 1)——(x ^ 7 + x + 1)= x ^ 7 + x ^ 6 + x ^ 4 + x ^ 2
两个多项式的乘法是用通常的方法做的(当然，系数的加法是通过模2来完成的)。
(x x ^ ^ 6 + 4 + x ^ 2 + x + 1)(x ^ 7 + x + 1)= x ^ 13 + x ^ 11 + x ^ 9 + x x ^ ^ 8 + 6 + x x ^ ^ 5 + 4 + x ^ 3 + 1
两个多项式f(x)和g(x)的乘法运算(x)是f(x)g(x)除以h(x)的余数。
(x x ^ ^ 6 + 4 + x ^ 2 + x + 1)(x ^ 7 + x + 1)模(x x ^ ^ 8 + 4 + x ^ 3 + x + 1)= x ^ 7 + x ^ 6 + 1
多项式的最大指数叫做它的次数。例如,x ^ 7度+ x ^ 6 + 1 = 7。

给定三个多项式f(x)、g(x)和h(x)，你要编写一个计算f(x)g(x)模h(x)的程序。
我们假设f(x)和g(x)的度数都小于h(x)的度数。多项式的次数小于1000次。
因为一个多项式的系数是0或1，一个多项式可以用d+1和一个长d+1的位串来表示，其中d是多项式的次数，而位串表示多项式的系数。例如,x ^ 7 + x ^ 6 + 1可以用8 1 1 0 0 0 0 0 1。
输入
输入由T测试用例组成。在输入文件的第一行中给出了测试用例(T)的数量。每个测试用例由三行组成，每一行包含三个多项式f(x)、g(x)和h(x)。每个多项式都是如上所述表示的。
输出

输出应该包含多项式f(x)g(x)模块化h(x)，每行一个。

样例输入

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 

#include <iostream>
#include <stdio.h>
#include <string.h>using namespace std;
const int maxn=2010;
//f,g,h存储的是多项式的系数,sum存储的是f*g的系数以及最后余数的系数
int f[maxn],g[maxn],h[maxn],sum[maxn];
int lf,lg,lh,ls;//分别为f,g,h,sum的最高次幂//比较sum表示的多项式与h表示的多项式的大小
int compare() {if(ls<lh)return -1;if(ls>lh)return 1;for(int i=ls-1; i>=0; i--) { //如果最高次幂相等，则从高位向下依次比较if(sum[i]==h[i])continue;if(sum[i]>h[i])return 1;if(sum[i]<h[i])return -1;}return 0;
}
int main() {int t,d;scanf("%d",&t);while(t--) {memset(h,0,sizeof(h));memset(sum,0,sizeof(sum));//将f多项式的信息存入f数组scanf("%d",&d);lf=d-1;for(int j=lf; j>=0; j--) {scanf("%d",&f[j]);}//将g多项式的信息存入g数组scanf("%d",&d);lg=d-1;for(int j=lg; j>=0; j--) {scanf("%d",&g[j]);}//将h多项式的信息存入h数组scanf("%d",&d);lh=d-1;for(int j=lh; j>=0; j--) {scanf("%d",&h[j]);}//计算f*g的多项式ls=lf+lg;for(int i=lf; i>=0; i--) {for(int j=lg; j>=0; j--) {sum[i+j]=sum[i+j]^(f[i]&g[j]);}}/*关键是怎么求余数，这里是先判断sum多项式是否大于h多项式，若大于，则sum减一次h，减去后的信息存入sum中。再继续判断,直到sum小于h，则此时的sum为余数。总之，就是把除法改成较简单的减法操作。*/while(compare()>=0) {d=ls-lh;for(int i=ls; i-d>=0; i--) {sum[i]=sum[i]^h[i-d];}while(ls && !sum[ls])ls--;}printf("%d",ls+1);for(int i=ls; i>=0; i--) {printf(" %d",sum[i]);}printf("\n");}return 0;
}

主要在于把除法转化成减法，一次一次减。

用sum[]数组存结果，最高次幂为ls，各项系数存在f[ls-1 … 0]

1 - 计算乘积，

多项式的系数只有1或0，故最高次幂ls = lf + lg -1，f[i]*g[j]（i、j为指数的值），相当于位的与运算f[i]&g[j]，结果加到x^(i+j)的系数上，即sum[i+j]+=f[i]&g[j]；

2 - 计算模除。

sum(x)对h(x)取模，即除以h(x)直到余数小于h(x)，此余数即取模的结果，关键在于判别sum(x)、h(x)的大小。

若ls>lh，则sum大；让sum(x)除以h(x)：

对h，按次幂由低到高，进行相除运算，h[i]异或到sum[i+ls-lh]，即sum[i+d] ^= h[i]，然后重新调整sum的最高次幂（while(ls&&!sum[ls-1])-ls）

ls<lh，则h大，得到结果；

若ls=lh，从最高次幂开始逐项比较系数。