Submission #70983599

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int mod = 998244353;
const int g = 3;
const int v_max = 500000;

vector<ll> fact(v_max + 1);
vector<ll> invfact(v_max + 1);

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

ll modInverse(ll n) {
    return power(n, mod - 2);
}

void bit_reversal(vector<ll>& a, int n, int log_n) {
    for (int i = 0; i < n; ++i) {
        int rev = 0;
        for (int j = 0; j < log_n; ++j) {
            if ((i >> j) & 1) {
                rev |= (1 << (log_n - 1 - j));
            }
        }
        if (i < rev) {
            swap(a[i], a[rev]);
        }
    }
}

void ntt(vector<ll>& a, bool invert) {
    int n = a.size();
    int log_n = 0;
    while ((1 << log_n) < n) log_n++;

    bit_reversal(a, n, log_n);

    for (int len = 2; len <= n; len <<= 1) {
        ll wlen = power(g, (mod - 1) / len);
        if (invert) {
            wlen = modInverse(wlen);
        }

        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int j = 0; j < len / 2; ++j) {
                ll u = a[i + j];
                ll v = (a[i + j + len / 2] * w) % mod;

                a[i + j] = (u + v) % mod;
                a[i + j + len / 2] = (u - v + mod) % mod;

                w = (w * wlen) % mod;
            }
        }
    }

    if (invert) {
        ll n_inv = modInverse(n);
        for (int i = 0; i < n; ++i) {
            a[i] = (a[i] * n_inv) % mod;
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;

    fact[0] = 1;
    invfact[0] = 1;
    for (int i = 1; i <= v_max; ++i) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    invfact[v_max] = modInverse(fact[v_max]);
    for (int i = v_max - 1; i >= 1; --i) {
        invfact[i] = (invfact[i + 1] * (i + 1)) % mod;
    }

    vector<int> count_a(v_max + 1, 0);
    vector<int> count_b(v_max + 1, 0);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        count_a[x]++;
    }
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        count_b[x]++;
    }

    int l = 1;
    while (l <= 2 * v_max) {
        l <<= 1;
    }

    vector<ll> poly_p(l, 0);
    vector<ll> poly_q(l, 0);

    for (int k = 0; k <= v_max; ++k) {
        int i = v_max - k;
        poly_p[k] = (static_cast<ll>(count_a[i]) * fact[i]) % mod;
    }

    for (int j = 0; j <= v_max; ++j) {
        poly_q[j] = (static_cast<ll>(count_b[j]) * invfact[j]) % mod;
    }

    ntt(poly_p, false);
    ntt(poly_q, false);

    vector<ll> poly_r(l);
    for (int i = 0; i < l; ++i) {
        poly_r[i] = (poly_p[i] * poly_q[i]) % mod;
    }

    ntt(poly_r, true);

    ll totalsum = 0;
    for (int k = 0; k <= v_max; ++k) {
        ll c_k = poly_r[v_max - k];
        ll h_k = invfact[k];

        totalsum = (totalsum + c_k * h_k) % mod;
    }

    cout << totalsum << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--) solve();
    return 0;
}

Submission Info

Judge Result