UOJ#34. 多项式乘法
题意：
给你两个多项式，请输出乘起来后的多项式。
输入格式
第一行两个整数 n 和 m，分别表示两个多项式的次数。 第二行 n+1 个整数，表示第一个多项式的 0 到 n 次项系数。 第三行 m+1 个整数，表示第二个多项式的 0 到 m 次项系数。
输出格式
一行 n+m+1 个整数，表示乘起来后的多项式的 0 到 n+m 次项系数。
code：
#include<bits/stdc++.h>
using namespace std
;
const int maxm
=4e5+5;
const int mod
=998244353;
const int G
=3;
int rev
[maxm
];
int a
[maxm
];
int b
[maxm
];
int n
,m
;
int ppow(int a
,int b
,int mod
){
int ans
=1%mod
;a
%=mod
;
while(b
){
if(b
&1)ans
=1ll*ans
*a
%mod
;
a
=1ll*a
*a
%mod
;
b
>>=1;
}
return ans
;
}
void ntt(int a
[],int len
,int on
){
for(int i
=0;i
<len
;i
++)if(i
<rev
[i
])swap(a
[i
],a
[rev
[i
]]);
for(int i
=1;i
<len
;i
<<=1){
int wn
=ppow(G
,(mod
-1)/(i
<<1),mod
);
if(on
==-1)wn
=ppow(wn
,mod
-2,mod
);
for(int j
=0;j
<len
;j
+=(i
<<1)){
int w
=1;
for(int k
=0;k
<i
;k
++){
int x
=a
[j
+k
],y
=1ll*w
*a
[i
+j
+k
]%mod
;
a
[j
+k
]=((1ll*x
+y
)%mod
+mod
)%mod
;
a
[i
+j
+k
]=(1ll*x
-y
+mod
)%mod
;
w
=1ll*w
*wn
%mod
;
}
}
}
if(on
==-1){
int inv
=ppow(len
,mod
-2,mod
);
for(int i
=0;i
<len
;i
++)a
[i
]=1ll*a
[i
]*inv
%mod
;
}
}
signed main(){
scanf("%d%d",&n
,&m
);
for(int i
=0;i
<=n
;i
++)scanf("%d",&a
[i
]);
for(int i
=0;i
<=m
;i
++)scanf("%d",&b
[i
]);
int len
=1,l
=0;
while(len
<=m
+n
)len
<<=1,l
++;
for(int i
=0;i
<len
;i
++){
rev
[i
]=(rev
[i
>>1]>>1)|((i
&1)<<(l
-1));
}
ntt(a
,len
,1);
ntt(b
,len
,1);
for(int i
=0;i
<len
;i
++)a
[i
]=1ll*a
[i
]*b
[i
]%mod
;
ntt(a
,len
,-1);
len
=n
+m
;
for(int i
=0;i
<=n
+m
;i
++){
printf("%d ",a
[i
]);
}
return 0;
}
