UOJ#34. 多项式乘法

这是一道模板题。

给你两个多项式，请输出乘起来后的多项式。

输入格式

第一行两个整数

第二行

第三行

输出格式

一行

样例一

input

1 2
1 2
1 2 1

output

1 4 5 2

explanation

限制与约定

时间限制：

空间限制：

数学问题 NTT快速数论变换

模板题

NTT用数论中的原根代替了FFT中的复数，规避了复数运算的精度误差，但只能在模意义下进行。

如果模数很大而最终运算结果较小，也可以当做非模意义下的运算来用。（比如说这道题）

代码和FFT差不多，只是原先是复数运算的地方改掉了。

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 #define LL long long
 9 using namespace std;
10 const double pi=acos(-1.0);
11 const int mod=479*(1<<21)+1;
12 const int MOD=479*(1<<21)+1;
13 const int mxn=400010;
14 int ksm(int a,int k){
15     int res=1;
16     while(k){
17         if(k&1)res=((LL)res*a)%mod;
18         a=((LL)a*a)%mod;
19         k>>=1;
20     }
21     return res;
22 }
23 int n,l;
24 int a[mxn],b[mxn],rev[mxn];
25 //
26 void NTT(int *a,int flag){
27     int i,j,k;
28     for(i=0;i<n;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);
29     for(i=1;i<n;i<<=1){
30         int gn=ksm(3,(mod-1)/(i<<1));
31         int p=i<<1;
32         for(j=0;j<n;j+=p){
33             int g=1;
34             for(k=0;k<i;k++,g=((LL)g*gn)%mod){
35                 int x=a[j+k],y=((LL)g*a[i+j+k])%mod;
36                 a[j+k]=(x+y)%mod;
37                 a[i+j+k]=(x-y+mod)%mod;
38             }
39         }
40     }
41     if(flag==-1){
42         reverse(a+1,a+n);
43         int inv=ksm(n,mod-2);
44         for(i=0;i<n;i++)a[i]=((LL)a[i]*inv)%mod;
45     }
46     return;
47 }
48 char s1[mxn],s2[mxn];
49 int N,M;
50 int main(){
51     int i,j;
52     scanf("%d%d",&N,&M);
53     for(i=0;i<=N;i++)scanf("%d",&a[i]);
54     for(i=0;i<=M;i++)scanf("%d",&b[i]);
55 //    scanf("%s",s1);
56 //    scanf("%s",s2);
57 //    for(i=0;i<N;i++)a[i]=s1[i]-'0';
58 //    for(i=0;i<M;i++)b[i]=s2[i]-'0';
59     int m=N+M;
60     for(n=1;n<=m;n<<=1)l++;
61     for(i=0;i<n;i++){
62         rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
63     }
64     NTT(a,1);NTT(b,1);
65     for(i=0;i<n;i++)a[i]=((LL)a[i]*b[i]%mod);
66 //    for(i=0;i<n;i++)printf("%d ",a[i]);
67 //    printf("
");
68     NTT(a,-1);
69     for(i=0;i<=m;i++){
70         printf("%d ",a[i]);
71     }
72     return 0;
73 }