題解:https://www.luogu.org/problemnew/show/P3803
題解:直接做是n^2的。可以用FFT優化。首先要知道一些知識。
一.機關複數根
定義:
。
表示機關複數根，相當于将複平面的機關圓等分成n份(n一般是2的多少次幂)，從實數軸逆時針旋轉對應的坐标。
性質：
,
。還是很容易推出來的。
二.點值表示法
一個n次多項式可以用n個坐标來代替。我們用機關複數根來當做坐标，要求出函數值。設:
奇偶分類:
将w(k,n)代入看、k<n/2
将w(k+n/2,n)代入
注意到上面兩個式子隻有一個符号不同，是以通過枚舉第一個式子可以O(1)的求出另一個，這樣規模就減半了。
三.逆變換
設:
。
。
四.疊代實作
通過觀察性質，反轉後的序列就是原序列的下标的二進制反轉。我們用數位dp的思想。r[i]表示将i翻轉後的下标。例如11001->10011。其實就是将最右邊的1移到最高位，剩下的1100已經在之前做過了，直接将兩部分合并就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const double pi=acos(-1);
struct cp{
double r,i;
cp(){}
cp(double x,double y){
r=x;i=y;
}
cp operator +(const cp &a) const {
return cp(r+a.r,i+a.i);
}
cp operator - (const cp &a) const{
return cp(r-a.r,i-a.i);
}
cp operator * (const cp &a)const {
return cp(r*a.r-i*a.i,r*a.i+i*a.r);
}
}a[N<<2],b[N<<2];
int R[N<<2];//反碼
int n,m,L;
inline void fft(cp *a,int len,int op){
for(int i=0;i<len;i++) {
if(i<R[i]) swap(a[ i ],a[ R[i] ]);
}
for(int i=2;i<=len;i<<=1){//
cp wn=cp(cos(2*pi/i), op*sin(2*pi/i));//機關複數根
for(int j=0;j<len;j+=i){
cp w=cp(1.0,0.0);
for(int k=j;k<j+(i/2);k++,w=w*wn){
cp u=a[k];
cp v=w*a[k+i/2];
a[k]=u+v;
a[k+i/2]=u-v;
}
}
}
if(op==-1) for(int i=0;i<len;i++) a[i].r/=len;
}
int main(){
// cp a=cp(1.0,2.0);
// cp b=cp(1.0,2.0);
// cp c=a*b;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) scanf("%lf",&a[i].r);
for(int i=0;i<=m;i++) scanf("%lf",&b[i].r);
// 初始化
m+=n;n=1;L=0;
for(;n<=m;n<<=1)L++;
for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);
fft(a,n,1);fft(b,n,1);
for(int i=0;i<n;i++) a[i]=a[i]*b[i];
fft(a,n,-1);
for(int i=0;i<=m;i++) printf("%d ",(int)(a[i].r+0.5));//四舍五入
return 0;
}
/*
3 4
1 2 3 4
1 2 3 4 5
//0 4 2 6 1 5 3 7 R[i] n=8
*/