NTT,WA0pts玄关求条
查看原帖
NTT,WA0pts玄关求条
748238
ghx0052楼主2024/10/21 20:52
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 998244353, Gi = 332748118, G = 3;

ll a[3000100], b[3000010];
ll rev[3000010], pow3[3000010], pow3inv[3000010];

inline ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

inline void init(int l, int cnt) {
    for (int i = 1; i < l; i ++) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1)); 
}

inline void __pow3(int l) {
    for (int i = 1; i <= l; i <<= 1) pow3[i] = qpow(G, (mod - 1) / i);
    for (int i = 1; i <= l; i <<= 1) pow3inv[i] = qpow(pow3[i], mod - 2);
}

inline void NTT(ll *a, int n, ll inv) {
    for (int i = 1; i < n; i ++) 
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 2; i <= n; i <<= 1) {
        ll m = i >> 1, wn = pow3[i];
        if (inv == -1) wn = pow3inv[i];
        for (int j = 0; j < n; j += i) {
            ll w = 1;
            for (int k = 0; k < m; k ++, w = (ll)w * wn % mod) {
                ll x = a[j + k], y = (ll)w * a[j + k + i] % mod;
                a[j + k] = (x + y) % mod;
                a[j + k + i] = (ll)(x - y + mod) % mod;
            }
        }
    }
    if (inv == -1) {
        ll inv1 = qpow(n, mod - 2);
        for (int i = 0; i < n; i ++) a[i] = (ll)a[i] * inv1 % mod;
    }  
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    for (int i = 0; i < n; i ++) a[i] = s1[n - i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m - i] - '0';
    int l = 1, cnt = 0;
    while (l <= n + m) l <<= 1, cnt ++;
    __pow3(l);
    init(l, cnt);
    NTT(a, l, 1);
    NTT(b, l, 1);
    for (int i = 0; i < l; i ++) a[i] = (ll)a[i] * b[i] % mod;
    NTT(a, l, -1);
    for (int i = 0; i < l; i ++) 
        if (a[i] > 9) a[i + 1] += a[i] / 10, a[i] %= 10;
    int k = l - 1;
    while (a[k] == 0) k --;
    for (int i = k; i >= 0; i --) cout << a[i];
}
2024/10/21 20:52
加载中...