Submission #17079072

---

Source Code Expand

#include <bits/stdc++.h>
using i64 = long long;

constexpr i64 mod = 998244353;

std::vector<long long> fact, inv;

constexpr auto pow(long long x, long long n, const long long mod) {
    long long ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

constexpr auto inverse(const long long x, const long long p) {
    return pow(x, p - 2, p);
}

void init_factorial(const int n, const long long mod) {
    fact.resize(n + 1);
    inv.resize(n + 1);
    fact[0] = 1;
    for (long long i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv[n] = inverse(fact[n], mod);
    for (long long i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

std::vector<i64> roots, rootsinv;

void calc_roots(const int n) {
    int sz = 0;
    while ((1 << sz) <= n) sz++;
    roots.resize(sz);
    rootsinv.resize(sz);

    for (int i = 1; i < sz; i++) roots[i] = pow(3, (mod - 1) / (1 << i), mod);
    for (int i = 1; i < sz; i++) rootsinv[i] = inverse(roots[i], mod);
}

void ntt(std::vector<i64> &a, bool rev = false) {
    const i64 n = a.size();
    if (roots.empty()) calc_roots(100100);

    for (int i = 0, j = 1; j < n - 1; j++) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1);
        if (j < i) std::swap(a[i], a[j]);
    }

    for (int mi = 1; (1 << mi) <= n; mi++) {
        const int m = 1 << mi;
        const i64 cc = rev ? rootsinv[mi] : roots[mi];

        for (int i = 0; i < n; i += m) {
            i64 w = 1;
            for (int j = i, k = i + m / 2; k < i + m; j++, k++) {
                i64 t1 = a[j], t2 = w * a[k] % mod;
                a[j] = (t1 + t2) % mod;
                a[k] = (t1 + mod - t2) % mod;
                w = w * cc % mod;
            }
        }
    }

    if (rev) {
        const i64 rv = inverse(n, mod);
        for (int i = 0; i < n; i++) a[i] = a[i] * rv % mod;
    }
}

std::vector<i64> multiply(std::vector<i64> f, std::vector<i64> g) {
    int maxindex = f.size() + g.size() + 1;
    int s = 1;
    while (s < maxindex) s *= 2;
    f.resize(s);
    g.resize(s);

    ntt(f);
    ntt(g);

    for (int i = 0; i < f.size(); i++) f[i] = f[i] * g[i] % mod;
    ntt(f, true);
    while (f.size() > 1 && f.back() == 0) f.pop_back();
    return f;
}

struct Comp {
    bool operator()(const std::vector<i64> &lhs, const std::vector<i64> &rhs) const {
        return lhs.size() < rhs.size();
    }
};

int main() {
    int n;
    std::cin >> n;
    init_factorial(2 * n, mod);
    std::vector<i64> cnt(100100);
    for (int i = 0; i < 2 * n; i++) {
        int a;
        std::cin >> a;
        cnt[a]++;
    }

    constexpr i64 i2 = inverse(2, mod);

    std::multiset<std::vector<i64>, Comp> ss;
    for (const auto e : cnt) {
        if (!e) continue;
        std::vector<i64> co;
        i64 q = 1;
        for (int i = 0; 2 * i <= e; i++) {
            const i64 c = fact[e] * inv[e - 2 * i] % mod * inv[i] % mod * q % mod;
            co.push_back(c);
            q = q * i2 % mod;
        }
        ss.insert(co);
    }

    while (ss.size() > 1) {
        const auto f = std::move(ss.extract(ss.begin()).value());
        const auto g = std::move(ss.extract(ss.begin()).value());
        const auto &&h = multiply(f, g);
        ss.insert(h);
    }

    const auto &v = *ss.begin();
    i64 d = inverse(pow(2, n, mod), mod), ret = 0;
    for (int i = 0; i < v.size(); i++) {
        const i64 x = fact[2 * (n - i)] * d % mod * inv[n - i] % mod;
        if (i % 2 == 0) ret = (ret + x * v[i] % mod) % mod;
        else ret = (ret + mod - x * v[i] % mod) % mod;
        d = d * 2 % mod;
    }

    std::cout << ret << std::endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘std::vector<long long int> multiply(std::vector<long long int>, std::vector<long long int>)’:
./Main.cpp:83:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   83 |     for (int i = 0; i < f.size(); i++) f[i] = f[i] * g[i] % mod;
      |                     ~~^~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:130:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  130 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Judge Result