結果

問題 No.3123 Inversion
コンテスト
ユーザー 👑 ramdos
提出日時 2025-12-09 22:50:23
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 780 ms / 10,000 ms
コード長 2,627 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,011 ms
コンパイル使用メモリ 198,692 KB
実行使用メモリ 80,444 KB
最終ジャッジ日時 2025-12-09 22:50:48
合計ジャッジ時間 24,511 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// generated by GPT 5 pro
// LLMの作問能力評価のために自動生成された回答
// by CPCTF 運営チーム

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

using u32 = uint32_t;
using u64 = uint64_t;

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

    int T;
    u64 M;
    if (!(cin >> T >> M)) return 0;
    vector<int> Ns(T);
    int Nmax = 0;
    for (int i = 0; i < T; ++i) {
        cin >> Ns[i];
        if (Ns[i] > Nmax) Nmax = Ns[i];
    }
    if (M == 1) {
        for (int i = 0; i < T; ++i) cout << 0 << '\n';
        return 0;
    }

    // Precompute up to Nmax
    int Hmax = Nmax >> 1;       // floor(N/2)
    int Mmax = Nmax >> 2;       // floor(N/4)

    vector<u32> fact(Nmax + 1);
    fact[0] = 1 % M;
    for (int i = 1; i <= Nmax; ++i) {
        fact[i] = (u64)fact[i-1] * i % M;
    }

    vector<u32> invol(Nmax + 1);
    invol[0] = 1 % M;
    if (Nmax >= 1) invol[1] = 1 % M;
    for (int n = 2; n <= Nmax; ++n) {
        u64 term = (u64)(n - 1) * invol[n - 2] % M;
        invol[n] = (invol[n - 1] + term) % M;
    }

    vector<u32> S(Nmax + 1);
    S[0] = 1 % M;
    if (Nmax >= 1) S[1] = 1 % M;
    if (Nmax >= 2) S[2] = 2 % M;
    if (Nmax >= 3) S[3] = 2 % M;
    for (int n = 4; n <= Nmax; ++n) {
        int k = n - 2 - (n & 1); // N-3 if odd, N-2 if even
        u64 v = (2ULL * S[n - 2]) % M;
        v = (v + (u64)k * S[n - 4]) % M;
        S[n] = (u32)v;
    }

    // g[h] = 2^h * h!
    vector<u32> g(Hmax + 1);
    g[0] = 1 % M;
    for (int h = 1; h <= Hmax; ++h) {
        g[h] = (u64)g[h - 1] * (2ULL * h % M) % M;
    }

    // U[m] = (2m)! / m!  via U[m] = U[m-1] * (4m - 2)
    vector<u32> U(Mmax + 1);
    U[0] = 1 % M;
    for (int m = 1; m <= Mmax; ++m) {
        u64 mul = (4ULL * m - 2ULL) % M; // 4m - 2
        U[m] = (u64)U[m - 1] * mul % M;
    }

    // Answer queries
    for (int qi = 0; qi < T; ++qi) {
        int N = Ns[qi];
        u64 nf = fact[N];
        u64 I = invol[N];
        u64 Sn = S[N];
        u64 A = g[N >> 1];
        u64 Q = 0;
        if ((N & 3) <= 1) { // N % 4 == 0 or 1
            Q = U[N >> 2];
        }
        u64 delta = (N == 1) ? 1 : 0;

        // Ans = 8*N! - 8*I + 6*S - 4*A - 2*Q + delta  (mod M)
        long long res = 0;
        res += (long long)(8 % M) * nf % M;
        res -= (long long)(8 % M) * I % M;
        res += (long long)(6 % M) * Sn % M;
        res -= (long long)(4 % M) * A % M;
        res -= (long long)(2 % M) * Q % M;
        res += (long long)delta % M;
        res %= (long long)M;
        if (res < 0) res += M;
        cout << (u64)res % M << '\n';
    }
    return 0;
}
0