代码

/*******************************************
 * By Jerry Zheng
 * 
 * Get more points as possible.
 * Is the understanding of the statement correct?
 * If Subtask #2 is too hard, why not try Subtask #3?
 * 
 * Think twice, code once.
 * Are there any counterexamples to your algo?
 * Is the sol too heavy to debug?
 * Is the Time & Meomry complexity correct?
 * 
 * DON'T MAKE STUPID MISTAKES!!!!!
 * file-IO? DEBUG output? array size?
 * boundaries? long long?
 *
 *                             _ooOoo_
 *                            o8888888o
 *                            88" . "88
 *                            (| -_- |)
 *                            O\  =  /O
 *                         ____/`---'\____
 *                       .'  \|     |//  `.
 *                      /  \|||  :  |||//  \
 *                     /  _||||| -:- |||||-  \
 *                     |   | \\  -  /// |   |
 *                     | \_|  ''\---/''  |   |
 *                     \  .-\__  `-`  ___/-. /
 *                   ___`. .'  /--.--\  `. . __
 *                ."" '<  `.___\_<|>_/___.'  >'"".
 *               | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *               \  \ `-.   \_ __\ /__ _/   .-` /  /
 *          ======`-.____`-.___\_____/___.-`____.-'======
 *                             `=---='
 *          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 *                     佛祖保佑        永无BUG
*******************************************/

#include <bits/stdc++.h>

#define IL inline
#define CT const
#define RG register
#define TT template <typename Ty>
#define ll long long
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define LL long long

TT IL Ty max(const Ty& a, const Ty& b) { return a > b ? a : b; }
TT IL Ty min(const Ty& a, const Ty& b) { return a < b ? a : b; }
TT IL void cmax(Ty& a, const Ty& b) { if (b > a) a = b; }
TT IL void cmin(Ty& a, const Ty& b) { if (b < a) a = b; }
TT IL void swap(Ty& a, Ty& b) { Ty t = a; a = b; b = t; }
TT IL void swap(Ty*& a, Ty*& b) { Ty *t = a; a = b; b = t; }

namespace io {
const int MaxBuff = 1 << 15, MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b, buff[MaxOut], *iter = buff;
IL char getc() { return S == T && (T = (S = b) + fread(b, 1, MaxBuff, stdin), S == T) ? 0 : *S++; }
IL void putc(RG char ch) { *iter++ = ch; }
IL void fflush() { fwrite(buff, 1, iter - buff, stdout), iter = buff; }
} // namespace io

IL int getstr(RG char *s) {
    RG char *iter = s;
    while (*iter = io::getc(), *iter == ' ' || *iter == '\n' || *iter == '\r') ;
    while (*++iter = io::getc(), *iter && *iter != ' ' && *iter != '\n' && *iter != '\r') ;
    *iter = 0;
    return iter - s;
}

#define N 200005
const double pi = acos(-1.0);

struct comp { double x, y; } a[N], omg[N], inv[N];
#define comp(xx, yy) ((comp) { xx, yy })
IL comp operator +(CT comp &a, CT comp &b) { return comp(a.x + b.x, a.y + b.y); }
IL comp operator -(CT comp &a, CT comp &b) { return comp(a.x - b.x, a.y - b.y); }
IL comp operator *(CT comp &a, CT comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }

char s1[N], s2[N];
int len, n, rev[N], ans[N];

void FFT(int n, comp *a, comp *w) {
    for (int i = 0; i < n; i++)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int step = 1, ws = n >> 1; step < n; step <<= 1, ws >>= 1)
        for (int j = 0; j < n; j += step << 1)
            for (int k = j, wn = 0; k < j + step; k++, wn += ws) {
                comp x = a[k], y = w[wn] * a[k + step];
                a[k] = x + y, a[k + step] = x - y;
            }
}

int main() {
    len = 1e6, getstr(s1), getstr(s2);
    for (int i = len - 1, j = 0; i >= 0; i--, j++)
        a[j] = comp(s1[i] - '0', s2[i] - '0');
    int n = 1, lim = 0;
    while (n < len * 2)
        n <<= 1, lim++;
    lim--;
    for (int i = 0; i < n; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lim);
    for (int i = 0; i < n; i++) {
        omg[i] = comp(cos(2 * pi * i / n), sin(2 * pi * i / n));
        inv[i] = comp(cos(2 * pi * i / n), -sin(2 * pi * i / n));
    }
    FFT(n, a, omg);
    for (int i = 0; i < n; i++)
        a[i] = a[i] * a[i];
    FFT(n, a, inv);
    for (int i = 0; i < n; i++)
        ans[i] = round(a[i].y / n / 2);
    for (int i = 0; i < n; i++)
        if (ans[i] >= 10)
            ans[i + 1] += ans[i] / 10, ans[i] %= 10;
    while (ans[n] == 0 && n >= 1)
        n--;
    for (int i = n; i >= 0; i--)
        io::putc(ans[i] + '0'); 
    io::putc('\n');
    io::fflush();
    return 0;
}

评测结果