Description
请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ,并且有 n < = 10 ^ 5。 a,b中的元素均为小于等于100的非负整数。
Input
第一行一个整数N,接下来N行,第i+2..i+N-1行,每行两个数,依次表示a[i],b[i] (0 < = i < N)。
Output
输出N行,每行一个整数,第i行输出C[i-1]。
Sample Input
53 12 41 12 41 4
Sample Output
24121061
HINT
Source
先把b[i]变成b[n-i-1],所以C[k]=sigma(a[i]*b[n-i+k-1]),这就比较像卷积的形式了。
这时输出的变成了c[n-i]到c[n-i+n-1]。
code:
1 #include2 #include 3 #include 4 #include 5 #include 6 #define maxn 262144 7 #define pi 3.14159265358979323846 8 using namespace std; 9 char ch;10 int m,n;11 bool ok;12 void read(int &x){13 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;14 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());15 if (ok) x=-x;16 }17 struct comp{18 double rea,ima;19 comp operator +(const comp &x){ return (comp){rea+x.rea,ima+x.ima};}20 comp operator -(const comp &x){ return (comp){rea-x.rea,ima-x.ima};}21 comp operator *(const comp &x){ return (comp){rea*x.rea-ima*x.ima,rea*x.ima+ima*x.rea};}22 }a[maxn],b[maxn],c[maxn],tmp[maxn],w,wn;23 void fft(comp *a,int st,int siz,int step,int op){24 if (siz==1) return;25 fft(a,st,siz>>1,step<<1,op),fft(a,st+step,siz>>1,step<<1,op);26 int x=st,x1=st,x2=st+step;27 w=(comp){ 1,0},wn=(comp){cos(op*2*pi/siz),sin(op*2*pi/siz)};28 for (int i=0;i<(siz>>1);i++,x+=step,x1+=(step<<1),x2+=(step<<1),w=w*wn)29 tmp[x]=a[x1]+(w*a[x2]),tmp[x+(siz>>1)*step]=a[x1]-(w*a[x2]);30 for (int i=st;siz;i+=step,siz--) a[i]=tmp[i];31 }32 int main(){33 read(m),n=1;34 while (n<(m<<1)) n<<=1;35 for (int i=0;i