欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj2179 FFT快速傅立叶

程序员文章站 2022-05-09 18:27:09
2179: FFT快速傅立叶 Time Limit:10 SecMemory Limit:259 MB Submit:2372Solved:1182 [Submi...

2179: FFT快速傅立叶

Time Limit:10 SecMemory Limit:259 MB
Submit:2372Solved:1182
[Submit][Status][Discuss]

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

HINT

 

Source

#include
#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 200000
using namespace std;
const double pi=acos(-1.0);
int n,m,len,rev[maxn],ans[maxn];
char s[maxn];
struct cp
{
	double x,y;
	inline cp operator +(cp a){return (cp){x+a.x,y+a.y};}
	inline cp operator -(cp a){return (cp){x-a.x,y-a.y};}
	inline cp operator *(cp a){return (cp){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[maxn],b[maxn],c[maxn];
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[rev[i]],x[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>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;
			}
		}
	}
}
int main()
{
	n=read();
	scanf("%s",s);
	F(i,0,n-1) a[i].x=s[n-1-i]-'0';
	scanf("%s",s);
	F(i,0,n-1) b[i].x=s[n-1-i]-'0';
	m=1;n=2*n-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,n-1) ans[i]=(c[i].x/n)+0.5;
	F(i,0,n-1) ans[i+1]+=ans[i]/10,ans[i]%=10;
	n++;
	while (!ans[n]&&n) n--;
	D(i,n,0) putchar(ans[i]+'0');
	return 0;
}