結果

問題 No.3123 Inversion
ユーザー Kevgen
提出日時 2025-04-19 16:22:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,731 bytes
コンパイル時間 887 ms
コンパイル使用メモリ 73,840 KB
実行使用メモリ 43,072 KB
最終ジャッジ日時 2025-04-19 16:22:36
合計ジャッジ時間 24,456 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other RE * 14 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

const int max_n = 5e4 + 10;
vector<long long> fact(max_n);
vector<long long> inv_fact(max_n);
long long MOD;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

void precompute_factorials(int n, long long mod) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i-1] * i) % mod;
    }
    inv_fact[n] = power(fact[n], mod - 2, mod);
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = (inv_fact[i+1] * (i+1)) % mod;
    }
}

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

    int T;
    cin >> T >> MOD;

    precompute_factorials(max_n - 1, MOD);

    while (T--) {
        int N;
        cin >> N;

        if (N == 0) {
            cout << 1 % MOD << '\n';
            continue;
        }

        // Calculate the number of involutions (permutations where P^2 = identity)
        vector<long long> involution(N + 1, 0);
        involution[0] = 1;
        involution[1] = 1;
        for (int i = 2; i <= N; ++i) {
            involution[i] = (involution[i-1] + (i-1) * involution[i-2]) % MOD;
        }

        // Calculate the number of palindromic permutations (permutations where P = reverse(P))
        long long palindrome = 1;
        if (N % 2 == 0) {
            for (int i = 1; i <= N / 2; ++i) {
                palindrome = (palindrome * i) % MOD;
            }
            palindrome = (palindrome * palindrome) % MOD;
        } else {
            for (int i = 1; i <= (N + 1) / 2; ++i) {
                palindrome = (palindrome * i) % MOD;
            }
            palindrome = (palindrome * palindrome) % MOD;
            palindrome = (palindrome * inv_fact[(N + 1) / 2]) % MOD;
        }

        // Calculate the number of permutations fixed by inversion followed by reversal
        long long fixed = 1;
        if (N % 2 == 0) {
            for (int i = 1; i <= N / 2; ++i) {
                fixed = (fixed * i) % MOD;
            }
            fixed = (fixed * fixed) % MOD;
        } else {
            for (int i = 1; i <= (N + 1) / 2; ++i) {
                fixed = (fixed * i) % MOD;
            }
            fixed = (fixed * fixed) % MOD;
            fixed = (fixed * inv_fact[(N + 1) / 2]) % MOD;
        }

        // Total sum of orbit sizes using Burnside's Lemma
        long long total = (fact[N] + involution[N] + palindrome + fixed) % MOD;
        total = (total * power(4, MOD - 2, MOD)) % MOD;

        cout << total << '\n';
    }

    return 0;
}
0