結果

問題 No.3123 Inversion
コンテスト
ユーザー Kevgen
提出日時 2025-04-19 15:36:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,151 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 462,000 KB
最終ジャッジ日時 2025-04-19 15:37:49
合計ジャッジ時間 88,945 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

def main():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx += 1
    MOD = int(input[idx])
    idx += 1
    
    inv[1] = 1
    for i in range(2, max_n):
        inv[i] = MOD - MOD // i * inv[MOD % i] % MOD
    
    inv_fact[0] = 1
    for i in range(1, max_n):
        inv_fact[i] = inv_fact[i-1] * inv[i] % MOD
    
    for _ in range(T):
        N = int(input[idx])
        idx += 1
        
        if N == 0:
            print(1 % MOD)
            continue
        
        res = 1
        pow2 = 1
        term = 1
        for k in range(1, N//2 + 1):
            term = term * (N - 2*k + 1) * (N - 2*k + 2) % MOD
            term = term * inv[2 * k * (2 * k -1)] % MOD
            pow2 = pow2 * 2 % MOD
            res = (res + term * pow2) % MOD
        
        ans = res
        
        if N >= 1:
            ans = (ans + 1) % MOD
        
        if N % 2 == 1:
            ans = (ans - res * inv[N] % MOD) % MOD
        
        ans = (ans % MOD + MOD) % MOD
        print(ans)

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