結果

問題 No.3123 Inversion
コンテスト
ユーザー 👑 ramdos
提出日時 2025-12-09 22:49:54
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 647 ms / 10,000 ms
コード長 4,918 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,140 ms
コンパイル使用メモリ 201,916 KB
実行使用メモリ 77,508 KB
最終ジャッジ日時 2025-12-09 22:50:20
合計ジャッジ時間 25,068 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:91:5: warning: ‘M’ may be used uninitialized [-Wmaybe-uninitialized]
   91 |     if (M == 1) {
      |     ^~
main.cpp:83:14: note: ‘M’ was declared here
   83 |     uint32_t M;
      |              ^

ソースコード

diff #
raw source code 

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

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

struct FastScanner {
    static const size_t BUFSIZE = 1 << 20;
    int idx, size;
    char buf[BUFSIZE];
    FastScanner() : idx(0), size(0) {}
    inline char getChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }
    template<typename T>
    bool nextInt(T &out) {
        char c;
        T sign = 1;
        T val = 0;
        c = getChar();
        if (!c) return false;
        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
            if (!c) return false;
        }
        if (c == '-') {
            sign = -1;
            c = getChar();
        }
        for (; c >= '0' && c <= '9'; c = getChar())
            val = val * 10 + (c - '0');
        out = val * sign;
        return true;
    }
};

struct FastWriter {
    static const size_t BUFSIZE = 1 << 20;
    char buf[BUFSIZE];
    size_t idx;
    FastWriter() : idx(0) {}
    ~FastWriter() { flush(); }
    inline void pushChar(char c) {
        if (idx >= BUFSIZE) flush();
        buf[idx++] = c;
    }
    inline void writeUInt(uint32_t x) {
        char s[16];
        int n = 0;
        if (x == 0) {
            pushChar('0');
            pushChar('\n');
            return;
        }
        while (x) {
            s[n++] = char('0' + (x % 10));
            x /= 10;
        }
        while (n--) pushChar(s[n]);
        pushChar('\n');
    }
    inline void flush() {
        if (idx) {
            fwrite(buf, 1, idx, stdout);
            idx = 0;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    FastScanner fs;
    FastWriter fw;

    int T;
    uint32_t M;
    if (!fs.nextInt(T)) return 0;
    fs.nextInt(M);

    vector<int> Ns;
    Ns.reserve(T);
    int maxN = 0;

    if (M == 1) {
        // Everything is 0 mod 1
        for (int i = 0; i < T; ++i) {
            int N; fs.nextInt(N);
            fw.writeUInt(0);
        }
        return 0;
    }

    for (int i = 0; i < T; ++i) {
        int N; fs.nextInt(N);
        Ns.push_back(N);
        if (N > maxN) maxN = N;
    }

    int maxM = maxN / 2;

    // Precompute factorials up to maxN mod M
    vector<uint32_t> fact(maxN + 1);
    fact[0] = 1 % M;
    for (int i = 1; i <= maxN; ++i) {
        fact[i] = (uint64_t)fact[i - 1] * (uint64_t)i % M;
    }

    // Precompute involution counts A(n) up to maxN: A(0)=1, A(1)=1, A(n)=A(n-1)+(n-1)A(n-2)
    vector<uint32_t> invcnt(maxN + 1);
    invcnt[0] = 1 % M;
    if (maxN >= 1) invcnt[1] = 1 % M;
    for (int n = 2; n <= maxN; ++n) {
        uint64_t term = ((uint64_t)(n - 1) * invcnt[n - 2]) % M;
        uint64_t val = invcnt[n - 1] + term;
        if (val >= M) val -= M;
        invcnt[n] = (uint32_t)val;
    }

    // Precompute pow2 up to maxM
    vector<uint32_t> pow2(maxM + 1);
    pow2[0] = 1 % M;
    for (int i = 1; i <= maxM; ++i) pow2[i] = (pow2[i - 1] << 1) % M;

    // Precompute E(m): number of permutations commuting with J and involutive on 2m elements
    // E(0)=1, E(1)=2, E(m)=2 E(m-1) + 2 (m-1) E(m-2)
    vector<uint32_t> E(maxM + 1);
    E[0] = 1 % M;
    if (maxM >= 1) E[1] = 2 % M;
    for (int m = 2; m <= maxM; ++m) {
        uint64_t t1 = (2ULL * E[m - 1]) % M;
        uint64_t t2 = (2ULL * (m - 1)) % M;
        t2 = (t2 * E[m - 2]) % M;
        uint64_t val = t1 + t2;
        if (val >= M) val -= M;
        E[m] = (uint32_t)val;
    }

    // Precompute FD(m): number of permutations P with P^2 = J (J has m transpositions)
    // FD(0)=1, FD(1)=0, FD(m)=2 (m-1) FD(m-2)
    vector<uint32_t> FD(maxM + 1);
    FD[0] = 1 % M;
    if (maxM >= 1) FD[1] = 0;
    for (int m = 2; m <= maxM; ++m) {
        uint64_t val = (2ULL * (m - 1)) % M;
        val = (val * FD[m - 2]) % M;
        FD[m] = (uint32_t)val;
    }

    for (int i = 0; i < T; ++i) {
        int N = Ns[i];
        if (N == 1) {
            fw.writeUInt(1 % M);
            continue;
        }
        int m = N >> 1;

        uint64_t ans = 0;
        // + 8 * N!
        ans += (8ULL * fact[N]) % M;
        if (ans >= M) ans -= M;

        // - 8 * A(N)
        uint64_t t = (8ULL * invcnt[N]) % M;
        if (ans >= t) ans -= t;
        else ans = ans + M - t;

        // - 4 * (2^m * m!)
        uint64_t fr2 = (uint64_t)pow2[m] * fact[m] % M;
        t = (4ULL * fr2) % M;
        if (ans >= t) ans -= t;
        else ans = ans + M - t;

        // + 6 * E(m)
        t = (6ULL * E[m]) % M;
        ans += t;
        if (ans >= M) ans -= M;

        // - 2 * FD(m)
        t = (2ULL * FD[m]) % M;
        if (ans >= t) ans -= t;
        else ans = ans + M - t;

        fw.writeUInt((uint32_t)ans);
    }

    fw.flush();
    return 0;
}
0