Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

输出一行，即x*y的结果。（注意判断前导0）

输入输出样例

1
3
4

12

说明

数据范围：

n<=60000

来源：bzoj2179

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。

寻找了很久，最终还是发现算法导论的FFT讲解的是最详细的，前置技能：复数四则运算，矩阵基本运算。推荐这一篇博客：点击-> “这一篇博客”这样我们可以把一个数看成一个多项式(a1 * 10 ^ 0 + a2 * 10 ^ 1 + a3 * 10 ^ 2........)进行快速傅里叶变换，代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<complex>
#include<cmath>
#define Pi acos(-1)
using namespace std;
const int maxn = 2e6 + 5;
typedef complex<double> E;
E a[maxn << 1], b[maxn << 1];
int R[maxn << 1], ans[maxn << 1];
char s1[maxn], s2[maxn];
int n, m, x, l;

int FFT(E * a, int type) {
    /*按逆序归位*/
    for(register int i = 0; i < n; ++i) if(i < R[i]) swap(a[i], a[R[i]]);
    for(register int i = 1; i < n; i <<= 1) {
        E Wn(cos(Pi / i), sin(Pi * type / i));
        for(register int p = i << 1, j = 0; j < n; j += p) {
            E w(1, 0);
            for(register int k = 0; k < i; ++k, w *= Wn) {
                E x = a[j + k];
                E y = w * a[j + k + i];
                a[j + k] = x + y, a[j + k + i] = x - y;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    scanf("%s%s", s1, s2);
    n = strlen(s1), m = strlen(s2);
    for(register int i = --n; i >= 0; --i) a[n - i] = s1[i] - '0';
    for(register int i = --m; i >= 0; --i) b[m - i] = s2[i] - '0';
    m = n + m;
    for(n = 1; n <= m; n <<= 1) ++l;
    /*蝴蝶操作通过i >> 1的逆序递推i的逆序*/
    for(register int i = 0; i < n; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1));
    FFT(a, 1), FFT(b, 1);
    for(register int i = 0; i <= n; ++i) a[i] = a[i] * b[i];
    FFT(a, -1);
    for(register int i = 0; i < n; ++i) ans[i] = int(a[i].real() / n + 0.5);
    for(register int i = 0; i < n; ++i)
    	ans[i + 1] += ans[i] / 10, ans[i] = ans[i] % 10;
    int p = n;
    for(; p >= 0 && !ans[p]; --p);
    if(p == -1) {
    	printf("0");
    	return 0;
    }
    for(register int i = p; i >= 0; --i)
    	printf("%d", ans[i]);
    return 0;
}