結果

問題 No.3123 Inversion
ユーザー Kevgen
提出日時 2025-04-19 16:11:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,165 bytes
コンパイル時間 703 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 337,960 KB
最終ジャッジ日時 2025-04-19 16:12:12
合計ジャッジ時間 26,051 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 0
max_n = 5 * 10**6 + 10
fact = [1] * (max_n)
inv_fact = [1] * (max_n)

def main():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx += 1
    MOD = int(input[idx])
    idx += 1
    
    # Precompute factorials and inverse factorials modulo MOD
    for i in range(1, max_n):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact[max_n-1] = pow(fact[max_n-1], MOD-2, MOD)
    for i in range(max_n-2, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    for _ in range(T):
        N = int(input[idx])
        idx += 1
        
        if N == 0:
            print(1 % MOD)
            continue
        
        # Calculate the number of involutions (permutations where P^2 = identity)
        involution = [0] * (N + 1)
        involution[0] = 1
        involution[1] = 1
        for i in range(2, N + 1):
            involution[i] = (involution[i-1] + (i-1) * involution[i-2]) % MOD
        
        # Calculate the number of palindromic permutations (permutations where P = reverse(P))
        palindrome = 1
        if N % 2 == 0:
            for i in range(1, N // 2 + 1):
                palindrome = palindrome * i % MOD
            palindrome = palindrome * palindrome % MOD
        else:
            for i in range(1, (N + 1) // 2 + 1):
                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
        fixed = 1
        if N % 2 == 0:
            for i in range(1, N // 2 + 1):
                fixed = fixed * i % MOD
            fixed = fixed * fixed % MOD
        else:
            for i in range(1, (N + 1) // 2 + 1):
                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
        total = (fact[N] + involution[N] + palindrome + fixed) * pow(4, MOD-2, MOD) % MOD
        
        print(total)

if __name__ == "__main__":
    main()
0