【BZOJ-2179&2194】FFT快速傅里叶&快速傅里叶之二 FFT

时间：2021-08-19 22:29:52

2179: FFT快速傅立叶

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 2978  Solved: 1523
[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

2194: 快速傅立叶之二

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1101  Solved: 634
[Submit][Status][Discuss]

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

Sample Output

24
12
10
6
1

HINT

Source

Solution

RT..留个板子

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

struct Complex{

	double r,i;

	Complex (double R=0.0,double I=0.0) {r=R,i=I;}

	Complex operator + (Complex & A) const {return Complex(r+A.r,i+A.i);}

	Complex operator - (Complex & A) const {return Complex(r-A.r,i-A.i);}

	Complex operator * (Complex & A) const {return Complex(r*A.r-i*A.i,r*A.i+i*A.r);}

};

#define MAXN 600010

#define Pai acos(-1.0)

Complex A[MAXN],B[MAXN];

int len,N,ans[MAXN];

char s[MAXN];

inline void Prework()

{

	len=1;

	while (len < (N<<1)) len<<=1;  //扩展到2的幂次

	for (int i=N; i<len; i++) A[i]=Complex(0,0),B[i]=Complex(0,0); //补零

}

inline void Rader(Complex *x)

{

	for (int i=1,j=len>>1,k; i<len-1; i++)

		{

			if (i<j) swap(x[i],x[j]);

			k=len>>1;

			while (j>=k) j-=k,k>>=1;

			if (j<k) j+=k;

		}

}//位逆序置换

inline void DFT(Complex *x,int opt)

{

	Rader(x);

	for (int h=2; h<=len; h<<=1) //操作的长度，h=1不用管

		{

			Complex Wn( cos(opt*2*Pai/h) , sin(opt*2*Pai/h) );

			for (int i=0; i<len; i+=h)

				{

					Complex W(1,0);

					for (int j=i; j<i+h/2; j++)

						{

							Complex u=x[j],t=W*x[j+h/2];

							x[j]=u+t,x[j+h/2]=u-t; //蝴蝶操作

							W=W*Wn;

						}

				}

		}

	if (opt==-1) //插值时要/len

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

			x[i].r/=len;

}//opt=1 DFT opt=-1 IDFT

inline void FFT(Complex *A,Complex *B)

{

	DFT(A,1); DFT(B,1);

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

		A[i]=A[i]*B[i]; //点值乘

	DFT(A,-1);

}

int main()

{

	scanf("%d",&N);

	scanf("%s",s+1);

	for (int i=N,l=-1; i>=1; i--) A[++l].r=s[i]-'0';

	scanf("%s",s+1);

	for (int i=N,l=-1; i>=1; i--) B[++l].r=s[i]-'0';

	Prework();

	FFT(A,B);

	for (int i=0; i<len; i++) ans[i]=(int)(A[i].r+0.5);

	for (int i=0; i<len; i++) ans[i+1]+=ans[i]/10,ans[i]%=10;

	while (--len && !ans[len]);

	//高精乘的进位和去0

	for (int i=len; i>=0; i--) putchar(ans[i]+'0');

	puts("");

	return 0;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

struct Complex{

	double r,i;

	Complex (double R=0.0,double I=0.0) {r=R,i=I;}

	Complex operator + (Complex & A) const {return Complex(r+A.r,i+A.i);}

	Complex operator - (Complex & A) const {return Complex(r-A.r,i-A.i);}

	Complex operator * (Complex & A) const {return Complex(r*A.r-i*A.i,r*A.i+i*A.r);}

};

#define MAXN 600010

#define Pai acos(-1.0)

Complex A[MAXN],B[MAXN],C[MAXN];

int len,N,ans[MAXN],a[MAXN],b[MAXN];

char s[MAXN];

inline void Prework()

{

	len=1;

	while (len < (N<<1)) len<<=1;

	for (int i=N; i<len; i++) A[i]=Complex(0,0),B[i]=Complex(0,0);

}

inline void Rader(Complex *x)

{

	for (int i=1,j=len>>1,k; i<len-1; i++)

		{

			if (i<j) swap(x[i],x[j]);

			k=len>>1;

			while (j>=k) j-=k,k>>=1;

			if (j<k) j+=k;

		}

}

inline void DFT(Complex *x,int opt)

{

	Rader(x);

	for (int h=2; h<=len; h<<=1)

		{

			Complex Wn( cos(opt*2*Pai/h) , sin(opt*2*Pai/h) );

			for (int i=0; i<len; i+=h)

				{

					Complex W(1,0);

					for (int j=i; j<i+h/2; j++)

						{

							Complex u=x[j],t=W*x[j+h/2];

							x[j]=u+t,x[j+h/2]=u-t;

							W=W*Wn;

						}

				}

		}

	if (opt==-1)

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

			x[i].r/=len;

}

inline void FFT(Complex *A,Complex *B)

{

	DFT(A,1); DFT(B,1);

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

		C[i]=A[i]*B[i];

	DFT(C,-1);

}

int main()

{

	scanf("%d",&N);

	for (int i=1; i<=N; i++) scanf("%d%d",&a[i],&b[i]);

	for (int i=N,l=-1; i>=1; i--) A[++l].r=a[i];

	for (int i=1,l=-1; i<=N; i++) B[++l].r=b[i];

	Prework();	

	FFT(A,B);

	for (int i=0; i<len; i++) ans[i]=(int)(C[i].r+0.5); 

	for (int i=N-1; i>=0; i--) printf("%d\n",ans[i]);

	puts("");

	return 0;

}

　　

相关文章