HDU 1402 FFT 大数乘法

$A * B$
FFT模板题，找到了一个看起来很清爽的模板
/** @Date    : 2017-09-19 22:12:08

  * @FileName: HDU 1402 FFT 大整数乘法.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 2e5+20;

const double eps = 1e-8;

const double pi = acos(-1.0);

struct Complex

{

	double a, b;

	Complex(){}

	Complex(double _a, double _b):a(_a),b(_b){}

	Complex(double _a):a(_a),b(0.0){}

	inline Complex operator +(const Complex &z)const{

		return Complex(a + z.a, b + z.b);

	}

	inline Complex operator -(const Complex &z)const{

		return Complex(a - z.a, b - z.b);

	}

	inline Complex operator *(const Complex &z)const{

		return Complex(a * z.a - b * z.b, a * z.b + b * z.a);

	}

	inline Complex operator /(const Complex &z)const{

		double m = z.a * z.a + z.b * z.b;

		return Complex((a * z.a + b * z.b) / m, (z.a * b - z.b * a) / m);

	}

}A[N], B[N];

int L;

int rev[N];

int ans[N];

char a[N], b[N];

void init()

{

	MMF(A);

	MMF(B);

	MMF(ans);

	L = 0;//?

}

int reverse(int x,int r)  //蝴蝶操作

{

    int ans=0;

    for(int i=0; i<r; i++){

        if(x&(1<<i)){

            ans+=1<<(r-i-1);

        }

    }

    return ans;

}  

void rader(LL f[], int len)

{

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

	{

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

		int k = len >> 1;

		while(j >= k)

		{

			j -= k;

			k >>= 1;

		}

		if(j < k) j += k;

	}

}

void FFT(Complex c[], int nlen, int on)

{

	Complex wn, w, x, y;

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

		if(i < rev[i]) swap(c[i], c[rev[i]]);

	for(int i = 1; i < nlen; i <<= 1)

	{

		wn = Complex(cos(pi/i), sin(pi/i) * on);

		for(int p = i << 1, j = 0; j < nlen; j+= p)

		{

			w = Complex(1, 0);

			for(int k = 0; k < i; k++, w = w * wn)

			{

				x = c[j + k];

				y = w * c[j + k + i];

				c[j + k] = x + y;

				c[j + k + i] = x - y;

			}

		}

	}

	if(on == -1)

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

			c[i].a /= (double)nlen;

}

void work(Complex a[], Complex b[], int len)

{

	FFT(a, len, 1);

	FFT(b, len, 1);

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

		a[i] = a[i] * b[i];

	FFT(a, len, -1);

}

int main()

{

	while(~scanf("%s%s", a, b))

	{

		init();

		int alen = strlen(a);

		int blen = strlen(b);

		int len = alen + blen;

		//getlen

		int n;

		for(n = 1; n < len - 1; n <<= 1, L++);

		//rev

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

			rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (L - 1));

		//deal

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

			A[i] = a[alen - i - 1] - '0';

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

			B[i] = b[blen - i - 1] - '0';

		work(A, B, n);

		///

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

			ans[i] = (int)(A[i].a + 0.5);

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

			ans[i + 1] += ans[i] / 10, ans[i] %= 10;

		while(ans[len] == 0 && len)

			len--;

		for(int i = len; ~i; i--)

			printf("%c", ans[i] + '0');

		printf("\n");

	}

    return 0;

}
巴特西

HDU 1402 FFT 大数乘法

最新文章

热门文章
