bzoj 2194高速フーリエの2
2194:高速フーリエの2
Time Limit: 10 Sec
Memory Limit: 259 MB
Submit: 829
Solved: 474
[ Submit][ Status][ Discuss]
Description
C[k]=sigma(a[i]*b[i-k])のk<=iInput
第1行の整数N、次のN行、第i+2..i+N−1行、行ごとに2つの数、a[i],b[i](0<=iOutput
N行を出力し、行ごとに整数を1つ、i行目はC[i-1]を出力する.
Sample Input
5 3 1 2 4 1 1 2 4 1 4
Sample Output
24 12 10 6 1
問題の名前を見ると、この問題の方法がわかります.
これはボリュームの形式ではないので、2つの配列の1つを反転して、ボリュームの形式になります.そしてFFTで解決できます.
c[k]=Σ(a[i]*b[i-k])のような形で配列を反転させ、FFTを使用することができます.
Time Limit: 10 Sec
Memory Limit: 259 MB
Submit: 829
Solved: 474
[ Submit][ Status][ Discuss]
Description
C[k]=sigma(a[i]*b[i-k])のk<=i
第1行の整数N、次のN行、第i+2..i+N−1行、行ごとに2つの数、a[i],b[i](0<=i
N行を出力し、行ごとに整数を1つ、i行目はC[i-1]を出力する.
Sample Input
5 3 1 2 4 1 1 2 4 1 4
Sample Output
24 12 10 6 1
問題の名前を見ると、この問題の方法がわかります.
これはボリュームの形式ではないので、2つの配列の1つを反転して、ボリュームの形式になります.そしてFFTで解決できます.
c[k]=Σ(a[i]*b[i-k])のような形で配列を反転させ、FFTを使用することができます.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 300005
using namespace std;
int n,m,len,rev[maxn];
struct cp
{
double x,y;
inline cp operator +(cp b){return (cp){x+b.x,y+b.y};}
inline cp operator -(cp b){return (cp){x-b.x,y-b.y};}
inline cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};}
}a[maxn],b[maxn],c[maxn];
const double PI=acos(-1.0);
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void fft(cp *x,int n,int flag)
{
F(i,0,n-1) if (rev[i]>i) swap(x[i],x[rev[i]]);
for(int m=2;m<=n;m<<=1)
{
cp wn=(cp){cos(2.0*PI/m*flag),sin(2.0*PI/m*flag)};
for(int i=0;i<n;i+=m)
{
cp w=(cp){1.0,0};
int mid=m>>1;
F(j,0,mid-1)
{
cp u=x[i+j],v=x[i+j+mid]*w;
x[i+j]=u+v;x[i+j+mid]=u-v;
w=w*wn;
}
}
}
if(flag==-1) F(i,0,n-1) x[i].x/=n;
}
int main()
{
n=read();int nn=n;
F(i,0,n-1) a[i].x=read(),b[n-1-i].x=read();
n=2*n-1;m=1;
while (m<n) m<<=1,len++;
n=m;
F(i,0,n-1)
{
int t=i,ret=0;
F(j,1,len){ret<<=1;ret|=(t&1);t>>=1;}
rev[i]=ret;
}
fft(a,n,1);fft(b,n,1);
F(i,0,n-1) c[i]=a[i]*b[i];
fft(c,n,-1);
F(i,0,nn-1) printf("%lld
",(ll)(c[nn-1+i].x+0.5));
return 0;
}