POJ 2389 FFT

56 阅读 0 评论 37 点赞

我是靠谱客的博主欢呼板栗，最近开发中收集的这篇文章主要介绍POJ 2389 FFT，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

大致题意

求两个最高 40 位的十进制正整数相乘的结果。

题解

按位相乘 $O (n 2)$ ， $f f t$ 线性卷积长度 $L 1 + L 2 - 1$ ，从低位向前进位，排除前导零后倒着输出，复杂度 $O (n l o g n)$ 。

#include <cstdio>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <complex>
#define min(a,b)    (((a) < (b)) ? (a) : (b))
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define abs(x)    ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
#define eps 1e-3
#define PI 3.14159265358979323846
#define MAX_N 128
using namespace std;
// fft 模板
typedef complex<double> cp;
//二进制翻转; 正指数基; 负指数基
int rev[MAX_N];
cp pos[MAX_N], neg[MAX_N];
void fft_init(int n){
	int bit = 0;
	while((1 << bit) < n) ++bit;
	--bit;
	for(int i = 0; i < n; i++){
		rev[i] = rev[i >> 1] >> 1 | ((i & 1) << bit);
		pos[i] = cp(cos(2 * PI * i / n), sin(2 * PI * i /n));
		neg[i] = conj(pos[i]);
	}
}
void fft(cp *a, int n, cp *bas){
	for(int i = 0; i < n; i++){
		//避免重复交换
		if(i < rev[i]) swap(a[i], a[rev[i]]);
	}
	//fft 长度
	for(int l = 2; l <= n; l *= 2){
		int mid = l / 2;
		//各段 fft 起点
		for(cp *p = a; p != a + n; p += l){
			//蝶形运算
			for(int i = 0; i < mid; i++){
				cp t = bas[n * i / l] * p[i + mid];
				p[i + mid] = p[i] - t;
				p[i] += t;
			}
		}
	}
}

int main(){
	char s1[MAX_N], s2[MAX_N];
	while(~scanf("%s%s", s1, s2)){
		cp a[MAX_N], b[MAX_N];
		int res[MAX_N];
		int len1 = strlen(s1), len2 = strlen(s2), len = len1 + len2;
		for(int i = 0; i < len1; i++) a[i] = cp(s1[len1 - 1 - i] - '0', 0);
		for(int i = 0; i < len2; i++) b[i] = cp(s2[len2 - 1 - i] - '0', 0);
		//拓展为 2 ^ x
		int n = 1;
		while(n < len) n <<= 1;
		fft_init(n);
		fft(a, n, pos);
		fft(b, n, pos);
		for(int i = 0; i < n; i++) a[i] *= b[i];
		fft(a, n, neg);
		//线性卷积长度 L1 + L2 - 1
		memset(res, 0, sizeof(res));
		for(int i = 0; i < len - 1;i++){
			res[i] += floor(a[i].real() / n + 0.5);
			res[i + 1] += res[i] / 10;
			res[i] %= 10;
		}
		//避免输出前导零
		int f = len - 1;
		while(f > 0 && !res[f]) --f;
		for(int i = f; i >= 0; i--) putchar(res[i] + '0');
		putchar('n');
	}
	return 0;
}