「BZOJ2179」FFT快速傅立叶

2015年4月29日9,50411

Description

给出两个n位10进制整数x和y，你需要计算x*y。

Input

第一行一个正整数n。第二行描述一个位数为n的正整数x。第三行描述一个位数为n的正整数y。

Output

输出一行，即x*y的结果。

Sample Input

1
3
4

Sample Output

12
数据范围：
n<=60000

题解

2014.7.19

照着卓神的代码敲的

不要问我为何效率这么低QAQ

2015.4.29

重学FFT。。

zky神犇写的非常详细。。。

http://blog.csdn.net/iamzky/article/details/22712347

渣版

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<complex>
const double pi=3.14159265358979323;
using namespace std;
typedef vector<complex<double> > pl;
pl a,b,ans;
int n,c[140005];
char ch[70005];
void ini()
{
	scanf("%d",&n);
	scanf("%s",ch);
	for(int i=n-1;i>=0;i--)
        a.push_back(ch[i]-'0');
    scanf("%s",ch);
	for(int i=n-1;i>=0;i--)
        b.push_back(ch[i]-'0');
	n<<=1;
	int t=0;
	while((1<<t)<n)t++;
	n=(1<<t);
	a.resize(n);b.resize(n);
}
pl getpoint(pl x)
{
	int n=x.size();
	if(n>1)
	{
		pl l,r;
		for(int i=0;i<n;i+=2)
		{
			l.push_back(x[i]);
			r.push_back(x[i+1]);
		}
		complex<double> wn(cos(2*pi/n),sin(2*pi/n)),w(1,0);
		pl lp(getpoint(l)),rp(getpoint(r));
		for(int i=0;i<n/2;i++)
		{
			x[i]=lp[i]+w*rp[i];
			x[i+n/2]=lp[i]-w*rp[i];
			w*=wn;
		}
	}
	return x;
}
pl getvec(pl x)
{
	int n=x.size();
	if(n>1)
	{
		pl l,r;
		for(int i=0;i<n;i+=2)
		{
			l.push_back(x[i]);
			r.push_back(x[i+1]);
		}
		complex<double> wn(cos(2*pi*(n-1)/n),sin(2*pi*(n-1)/n)),w(1,0);
		pl lp(getvec(l)),rp(getvec(r));
		for(int i=0;i<n/2;i++)
		{
			x[i]=lp[i]+w*rp[i];
			x[i+n/2]=lp[i]-w*rp[i];
			w*=wn;
		}
	}
	return x;
}
void FFT()
{
	pl pa(getpoint(a)),pb(getpoint(b)),p(n);
	for(int i=0;i!=pa.size();i++)
	    p[i]=pa[i]*pb[i];
    pl ans(getvec(p));
    for(int i=0;i<=n-2;i++)
        c[i]=ans[i].real()/n+0.4;
    int l=0;
	for(int i=0;i<=n;i++)
    {
    	if(c[i])l=i;
    	c[i+1]+=c[i]/10;
    	c[i]%=10;
    }
    for(int i=l;i>=0;i--)
        printf("%d",c[i]);
}
int main()
{
	ini();
	FFT();
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<vector>

#include<algorithm>

#include<complex>

const double pi=3.14159265358979323;

using namespace std;

typedef vector<complex<double> > pl;

pl a,b,ans;

int n,c[140005];

char ch[70005];

void ini()

{

scanf("%d",&n);

scanf("%s",ch);

for(int i=n-1;i>=0;i--)

a.push_back(ch[i]-'0');

scanf("%s",ch);

for(int i=n-1;i>=0;i--)

b.push_back(ch[i]-'0');

n<<=1;

int t=0;

while((1<<t)<n)t++;

n=(1<<t);

a.resize(n);b.resize(n);

}

pl getpoint(pl x)

{

int n=x.size();

if(n>1)

{

pl l,r;

for(int i=0;i<n;i+=2)

{

l.push_back(x[i]);

r.push_back(x[i+1]);

}

complex<double> wn(cos(2*pi/n),sin(2*pi/n)),w(1,0);

pl lp(getpoint(l)),rp(getpoint(r));

for(int i=0;i<n/2;i++)

{

x[i]=lp[i]+w*rp[i];

x[i+n/2]=lp[i]-w*rp[i];

w*=wn;

}

return x;

}

pl getvec(pl x)

{

int n=x.size();

if(n>1)

{

pl l,r;

for(int i=0;i<n;i+=2)

{

l.push_back(x[i]);

r.push_back(x[i+1]);

}

complex<double> wn(cos(2*pi*(n-1)/n),sin(2*pi*(n-1)/n)),w(1,0);

pl lp(getvec(l)),rp(getvec(r));

for(int i=0;i<n/2;i++)

{

x[i]=lp[i]+w*rp[i];

x[i+n/2]=lp[i]-w*rp[i];

w*=wn;

}

return x;

}

void FFT()

{

pl pa(getpoint(a)),pb(getpoint(b)),p(n);

for(int i=0;i!=pa.size();i++)

p[i]=pa[i]*pb[i];

pl ans(getvec(p));

for(int i=0;i<=n-2;i++)

c[i]=ans[i].real()/n+0.4;

int l=0;

for(int i=0;i<=n;i++)

{

if(c[i])l=i;

c[i+1]+=c[i]/10;

c[i]%=10;

}

for(int i=l;i>=0;i--)

printf("%d",c[i]);

}

int main()

{

ini();

FFT();

return 0;

}

正常版。。。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define N 131072
#define pi acos(-1)
#define ll long long
using namespace std;
typedef complex<double> E;
int n,m,L;
char ch[N];
int R[N],c[N];
E a[N],b[N];
void fft(E *a,int f)
{
	for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
	for(int i=1;i<n;i<<=1)
	{
		E wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<n;j+=(i<<1))
		{
			E w(1,0);
			for(int k=0;k<i;k++,w*=wn)
			{
				E x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
	if(f==-1)for(int i=0;i<n;i++)a[i]/=n;
}
int main()
{
	scanf("%d",&n);n--;
    scanf("%s",ch);
	for(int i=0;i<=n;i++)a[i]=ch[n-i]-'0';
	scanf("%s",ch);
	for(int i=0;i<=n;i++)b[i]=ch[n-i]-'0';
	m=2*n;for(n=1;n<=m;n<<=1)L++;
	for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	fft(a,1);fft(b,1);
	for(int i=0;i<=n;i++)a[i]*=b[i];
	fft(a,-1);
	for(int i=0;i<=m;i++)c[i]=(int)(a[i].real()+0.1);
	for(int i=0;i<=m;i++)
		if(c[i]>=10)
		{
			c[i+1]+=c[i]/10,c[i]%=10;
			if(i==m)m++;
		}
	for(int i=m;i>=0;i--)printf("%d",c[i]);
	return 0;
}