#1152146 (C++14) No.3450 Permutation of Even Scores

• 問題: No.3450 Permutation of Even Scores
• ユーザー: fiblonaria
• 提出日時: 2026-03-11 12:04:30
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,024 ms / 2,000 ms
• コード長: 7,151 bytes
• コンパイル時間: 1,514 ms
• コンパイル使用メモリ: 200,488 KB
• 実行使用メモリ: 12,972 KB
• 最終ジャッジ日時: 2026-03-11 12:05:09
• 合計ジャッジ時間: 38,376 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 4
other	AC * 46

ソースコード

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

// ===============================================================
// ModInt: 998244353 上の四則演算
// ===============================================================
static const int MOD = 998244353;

struct Mint {
    int v;

    Mint(long long x = 0) {
        x %= MOD;
        if (x < 0) x += MOD;
        v = (int)x;
    }

    Mint& operator+=(const Mint& other) {
        v += other.v;
        if (v >= MOD) v -= MOD;
        return *this;
    }

    Mint& operator-=(const Mint& other) {
        v -= other.v;
        if (v < 0) v += MOD;
        return *this;
    }

    Mint& operator*=(const Mint& other) {
        v = (int)((long long)v * other.v % MOD);
        return *this;
    }

    friend Mint operator+(Mint a, const Mint& b) { return a += b; }
    friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
    friend Mint operator*(Mint a, const Mint& b) { return a *= b; }

    static Mint pow(Mint a, long long e) {
        Mint r = 1;
        while (e > 0) {
            if (e & 1) r *= a;
            a *= a;
            e >>= 1;
        }
        return r;
    }

    static Mint inv(Mint a) {
        return pow(a, MOD - 2);
    }

    Mint& operator/=(const Mint& other) {
        return *this *= inv(other);
    }

    friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

// ===============================================================
// NTT (Number Theoretic Transform)
// 998244353 は NTT 可能な法
// 原始根は 3
// ===============================================================
class NTT {
public:
    static void transform(vector<Mint>& a, bool invert) {
        int n = (int)a.size();

        // bit-reversal permutation
        for (int i = 1, j = 0; i < n; ++i) {
            int bit = n >> 1;
            while (j & bit) {
                j ^= bit;
                bit >>= 1;
            }
            j ^= bit;
            if (i < j) swap(a[i], a[j]);
        }

        // butterfly
        for (int len = 2; len <= n; len <<= 1) {
            Mint wlen = Mint::pow(3, (MOD - 1) / len);
            if (invert) wlen = Mint::inv(wlen);

            for (int i = 0; i < n; i += len) {
                Mint w = 1;
                for (int j = 0; j < len / 2; ++j) {
                    Mint u = a[i + j];
                    Mint t = a[i + j + len / 2] * w;
                    a[i + j] = u + t;
                    a[i + j + len / 2] = u - t;
                    w *= wlen;
                }
            }
        }

        if (invert) {
            Mint inv_n = Mint::inv(n);
            for (Mint& x : a) x *= inv_n;
        }
    }

    static vector<Mint> convolution(const vector<Mint>& a, const vector<Mint>& b) {
        if (a.empty() || b.empty()) return {};

        int need = (int)a.size() + (int)b.size() - 1;
        int n = 1;
        while (n < need) n <<= 1;

        vector<Mint> fa(a.begin(), a.end()), fb(b.begin(), b.end());
        fa.resize(n);
        fb.resize(n);

        transform(fa, false);
        transform(fb, false);
        for (int i = 0; i < n; ++i) fa[i] *= fb[i];
        transform(fa, true);

        fa.resize(need);
        return fa;
    }
};

// ===============================================================
// Solver
// ===============================================================
class Solver {
private:
    int N, M;
    vector<int> A;

    // is_target[x] = x が A の中に含まれるか
    vector<bool> is_target;

    // factorial
    vector<Mint> fact;

    // dp[x]:
    // 「選んだ A の部分集合の最大値が x」であるような部分集合の寄与総和
    // x ∈ A のときだけ意味があり、それ以外は 0
    vector<Mint> dp;

    // pending[x]:
    // dp[x] を確定させる前に、
    // 小さい y から来る Σ dp[y] * (x-y+1)! を蓄積しておく場所
    vector<Mint> pending;

private:
    void read_input() {
        cin >> N >> M;
        A.resize(M);
        for (int i = 0; i < M; ++i) cin >> A[i];
    }

    void build_factorials() {
        fact.assign(N + 2, Mint(1));
        for (int i = 1; i <= N + 1; ++i) {
            fact[i] = fact[i - 1] * Mint(i);
        }
    }

    void mark_targets() {
        is_target.assign(N + 1, false);
        for (int x : A) is_target[x] = true;
    }

    // -----------------------------------------------------------
    // 左半分 [l, mid] で確定した dp から、
    // 右半分 [mid+1, r] の pending に寄与をまとめて足す
    //
    // 必要な式:
    // pending[x] += Σ dp[y] * (x-y+1)!   (y < x)
    //
    // これは差 d = x-y に対して kernel[d] = (d+1)! という畳み込みになる。
    // ただし d=0 は使わないので kernel[0]=0 にしておく。
    // -----------------------------------------------------------
    void add_left_contribution_to_right(int l, int mid, int r) {
        vector<Mint> left_values(mid - l + 1);
        for (int i = l; i <= mid; ++i) {
            left_values[i - l] = dp[i];
        }

        vector<Mint> kernel(r - l + 1, Mint(0));
        for (int d = 1; d <= r - l; ++d) {
            kernel[d] = fact[d + 1];
        }

        vector<Mint> conv = NTT::convolution(left_values, kernel);

        // x に対応する添字は (x - l)
        for (int x = mid + 1; x <= r; ++x) {
            pending[x] += conv[x - l];
        }
    }

    // -----------------------------------------------------------
    // CDQ divide-and-conquer
    //
    // 再帰の葉 x で dp[x] を確定:
    //   dp[x] = -2 * ( x! + Σ_{y<x} dp[y] * (x-y+1)! )
    // -----------------------------------------------------------
    void cdq(int l, int r) {
        if (l == r) {
            if (is_target[l]) {
                dp[l] = Mint(-2) * (fact[l] + pending[l]);
            }
            return;
        }

        int mid = (l + r) >> 1;
        cdq(l, mid);
        add_left_contribution_to_right(l, mid, r);
        cdq(mid + 1, r);
    }

    // -----------------------------------------------------------
    // signed_sum = (#偶数スコア) - (#奇数スコア)
    //
    // 導出結果:
    // signed_sum = N! + Σ_{x in A} dp[x] * (N-x+1)!
    // -----------------------------------------------------------
    Mint compute_signed_sum() const {
        Mint signed_sum = fact[N];
        for (int x = 1; x <= N; ++x) {
            if (is_target[x]) {
                signed_sum += dp[x] * fact[N - x + 1];
            }
        }
        return signed_sum;
    }

public:
    void solve() {
        read_input();
        build_factorials();
        mark_targets();

        dp.assign(N + 1, Mint(0));
        pending.assign(N + 1, Mint(0));

        cdq(1, N);

        Mint total = fact[N];
        Mint signed_sum = compute_signed_sum();

        // even + odd = total
        // even - odd = signed_sum
        // よって even = (total + signed_sum) / 2
        Mint answer = (total + signed_sum) / Mint(2);
        cout << answer.v << '\n';
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Solver solver;
    solver.solve();
    return 0;
}