提交记录 12358


用户 题目 状态 得分 用时 内存 语言 代码长度
hly1204 1002. 测测你的多项式乘法 Accepted 100 176.457 ms 56988 KB C++11 1.78 KB
提交时间 评测时间
2020-03-27 00:21:56 2020-08-01 02:54:32
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 4e6 + 5;
using ll = long long;
const ll P = 119 << 23 | 1, G = 3;
ll eps[N], a1[N], a2[N];
ll qpow(ll x, ll y) {
    ll ans = 1;
    for (; y; y >>= 1, x = x * x % P) {
        if (y & 1) ans = ans * x % P;
    }
    return ans;
}
ll inv(ll x) { return qpow(x, P - 2); }
void init(int n) {
    ll g = qpow(G, (P - 1) / n);
    int l = n >> 1;
    for (int i = eps[l] = 1; i < l; ++i) {
        eps[l + i] = eps[l + i - 1] * g % P;
    }
    while (l >>= 1) {
        for (int i = 0; i < l; ++i) {
            eps[l + i] = eps[l + i << 1];
        }
    }
}
void dft(int n, ll x[]) { // output revbin
    for (int i = n; i >= 2; i >>= 1) {
        for (int j = 0, l = i >> 1; j < n; j += i) {
            for (int k = 0; k < l; ++k) {
                ll u = x[j + k], v = x[j + k + l];
                x[j + k] = (u + v) % P, x[j + k + l] = (u - v) * eps[l + k] % P;
            }
        }
    }
}
void idft(int n, ll x[]) { // input revbin
    for (int i = 2; i <= n; i <<= 1) {
        for (int j = 0, l = i >> 1; j < n; j += i) {
            for (int k = 0; k < l; ++k) {
                ll u = x[j + k], v = eps[l + k] * x[j + k + l];
                x[j + k] = (u + v) % P, x[j + k + l] = (u - v) % P;
            }
        }
    }
    reverse(x + 1, x + n);
    ll in = inv(n);
    for (int i = 0; i < n; ++i) x[i] = (x[i] + P) * in % P;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    for (int i = 0; i <= n; ++i) a1[i] = a[i];
    for (int i = 0; i <= m; ++i) a2[i] = b[i];
    int len = 1;
    while (len < n + m + 2) len <<= 1;
    init(len);
    dft(len, a1), dft(len, a2);
    for (int i = 0; i < len; ++i) (a1[i] *= a2[i]) %= P;
    idft(len, a1);
    for (int i = 0; i <= n + m; ++i) c[i] = a1[i];
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1176.457 ms55 MB + 668 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 16:26:00 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用