首页 > 代码库 > BZOJ2194: 快速傅立叶之二
BZOJ2194: 快速傅立叶之二
2194: 快速傅立叶之二
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 312 Solved: 173
[Submit][Status]
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
5
3 1
2 4
1 1
2 4
1 4
3 1
2 4
1 1
2 4
1 4
Sample Output
24
12
10
6
1
题解：
如果下标之和是定值，那么就是卷积了。但我门发现他们是下标之差是定值，那很容易，我们把其中一个数组翻转就可以用卷积了。
一开始没有计算完全2*n-2项，一直WA。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 200000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct cp 61 { 62 double x,y; 63 inline cp operator +(cp b){return (cp){x+b.x,y+b.y};} 64 inline cp operator -(cp b){return (cp){x-b.x,y-b.y};} 65 inline cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};} 66 }; 67 const double PI=acos(-1.0); 68 cp a[maxn],b[maxn],c[maxn],y[maxn]; 69 int n,m,len,rev[maxn],ans[maxn]; 70 char s[maxn]; 71 void fft(cp *x,int n,int flag) 72 { 73 for0(i,n-1)y[rev[i]]=x[i]; 74 for0(i,n-1)x[i]=y[i];//翻转 75 for(int m=2;m<=n;m<<=1) 76 { 77 cp wn=(cp){cos(2.0*PI/m*flag),sin(2.0*PI/m*flag)};//w（m，1） 78 for(int i=0;i<n;i+=m)//n个数按m个一份，每份内进行操作 79 { 80 cp w=(cp){1.0,0};int mid=m>>1; 81 for0(j,mid-1) 82 { 83 cp u=x[i+j],v=x[i+j+mid]*w; 84 x[i+j]=u+v;x[i+j+mid]=u-v; 85 w=w*wn; 86 }//蝴蝶操作 87 } 88 } 89 if(flag==-1)for0(i,n-1)x[i].x/=n; 90 } 91 92 int main() 93 94 { 95 96 freopen("input.txt","r",stdin); 97 98 freopen("output.txt","w",stdout); 99 100 n=read();101 for0(i,n-1)a[n-1-i].x=read(),b[i].x=read();102 n=2*n-1;103 m=1;104 while(m<n)m<<=1,len++;swap(n,m);105 for0(i,n-1)106 {107 int x=i,y=0;108 for1(j,len)y<<=1,y|=(x&1),x>>=1;109 rev[i]=y;110 }111 //for0(i,n-1)cout<<i<<‘ ‘<<a[i].x<<‘ ‘<<b[i].x<<endl;112 fft(a,n,1);fft(b,n,1);113 for0(i,n-1)c[i]=a[i]*b[i];114 fft(c,n,-1);115 //for0(i,n-1)cout<<i<<‘ ‘<<c[i].x<<endl;116 for3(i,(m-1)>>1,0)printf("%lld\n",(ll)(c[i].x+0.5));117 118 return 0;119 120 }
BZOJ2194: 快速傅立叶之二
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。