Отримання знань

дистанційна підтримка освіти школярів


Модульное умножение полиномов
http://acm.pku.edu.cn/JudgeOnline/problem?id=1060

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include "iostream.h" 
#include "string.h"
int fab(int a)
{
if(a >= 0) return a;
if(a < 0) return -a;
}
int main()
{
int a[1001],b[1001],c[1001],*r,n,i,j,flag,left,x,y,z,lcj;
cin >> n;
while(n--)
{
cin >> x;
for(i=x-1 ; i >= 0; i--)
cin >> a[i];
cin >> y;
for(i=y-1; i >= 0; i--)
cin >> b[i];
cin >> z;
for(i=z-1; i >= 0; i--)
cin >> c[i];
r=new int[x+y-1];
memset(r,0,sizeof(r));
for(i=0; i < x; i++)
for(j=0; j < y; j++)
{
r[i+j]+=a[i]*b[j];
}
for(i=0; i <= x+y-2; i++)
r[i]=fab(r[i])%2;
flag=x+y-2;
while(flag >= (z-1))
{
left=flag-z+1;
for(i=0;i < z; i++)
r[i+left]=r[i+left]-c[i];
lcj=0;
for(i=x+y-2; i >= 0; i--)
{r[i]=fab(r[i]);
if(r[i] != 0 && lcj == 0) {flag=i; lcj=1;}
}
}
for(i=0;i<=x+y-2;i++)
r[i]=fab(r[i])%2;
cout << flag+1 << " " << r[flag];
for(i = flag-1; i >= 0; i--)
cout << " " << r[i];
cout << endl;
}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)