提交记录 7960


用户 题目 状态 得分 用时 内存 语言 代码长度
1695651 1004. 【模板题】高精度乘法 Accepted 100 1.22 s 143236 KB C++ 1.63 KB
提交时间 评测时间
2019-01-25 23:17:15 2020-08-01 01:11:01
#include <bits/stdc++.h>
using namespace std;
typedef complex <double> cp;
const int N = 3e6 + 10;
const double PI = acos(-1);
int n = 1, lena, lenb, ans[N];
char *sa, *sb, s1[N], s2[N];
cp a[N], b[N], omg[N], inv[N];
inline void init(){
    for (int i = 0; i < n; i++){
        omg[i] = cp(cos(2 * PI * i / n), sin(2 * PI * i / n));
        inv[i] = conj(omg[i]);
    }
}
inline void fft(cp *a, cp *omg){
    int lim = 0;
    while ((1 << lim) < n) ++lim;
    for (int i = 0; i < n; i++){
        int t = 0;
        for (int j = 0; j < lim; j++)
            if (i & (1 << j)) t |= (1 << (lim - j - 1));
        if (t < i) swap(a[t], a[i]);
    }
    for (int l = 2; l <= n; l <<= 1){
        int m = l / 2;
        for (cp *p = a; p != a + n; p += l){
            for (int i = 0; i < m; i++){
                cp t = omg[n / l * i] * p[i + m];
                p[i + m] = p[i] - t;
                p[i] += t;
            }
        }
    }
}
int main(){
    scanf("%s %s", s1, s2);
    sa = s1; sb = s2;
    if (sa[0] == '0' || sb[0] == '0') {printf("0\n"); return 0;}
    lena = strlen(sa); lenb = strlen(sb);
    while (n < lena + lenb) n <<= 1;
    for (int i = 0; i < lena; i++) a[i].real(sa[lena - i - 1] - '0');
    for (int i = 0; i < lenb; i++) b[i].real(sb[lenb - i - 1] - '0');
    init();
    fft(a, omg);
    fft(b, omg);
    for (int i = 0; i < n; i++) a[i] *= b[i];
    fft(a, inv);
    for (int i = 0; i < n; i++){
        ans[i] += floor(a[i].real() / n + 0.5);
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    for (int i = ans[lena + lenb - 1] ? lena + lenb - 1 : lena + lenb - 2; i >= 0; i--)
        putchar(ans[i] + '0');
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.22 s139 MB + 900 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-23 13:33:56 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用