結果

問題 No.3123 Inversion
ユーザー keigo kuwata
提出日時 2025-04-23 09:01:50
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,763 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 819,120 KB
最終ジャッジ日時 2025-04-23 09:02:44
合計ジャッジ時間 52,629 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 5 MLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

def modinv(a, m):
    # m が素数の場合のフェルマーの小定理による逆元
    return pow(a, m-2, m)

def main():
    T, M = map(int, input().split())
    Ns = [int(input()) for _ in range(T)]
    maxN = max(Ns)

    # 1) 階乗と逆階乗
    fact = [1] * (maxN+1)
    for i in range(1, maxN+1):
        fact[i] = fact[i-1] * i % M
    ifact = [1] * (maxN+1)
    ifact[maxN] = modinv(fact[maxN], M)
    for i in range(maxN, 0, -1):
        ifact[i-1] = ifact[i] * i % M

    # 2) I[n] = 不動 2-置換（involution）の数
    I = [0] * (maxN+1)
    I[0] = 1
    if maxN >= 1:
        I[1] = 1
    for n in range(2, maxN+1):
        I[n] = (I[n-1] + (n-1) * I[n-2]) % M

    # 3) F2[n] = 180° 回転で不変な順列の数 = 2^(n//2)*( (n//2)! )
    F2 = [1] * (maxN+1)
    pow2 = 1
    half_fact = 1
    h = 0
    for n in range(1, maxN+1):
        if n % 2 == 0:
            h += 1
            pow2 = pow2 * 2 % M
            half_fact = half_fact * h % M
        F2[n] = pow2 * half_fact % M

    # 4) J[n] = binom(2*⌊n/2⌋, ⌊n/2⌋) mod M
    J = [1] * (maxN+1)
    for n in range(1, maxN+1):
        k = n // 2
        # fact[2k] * invfact[k]^2
        J[n] = fact[2*k] * ifact[k] % M * ifact[k] % M

    # 5) 各クエリに答える
    out = []
    for N in Ns:
        if N == 1:
            out.append("1")
            continue
        # 90° 回転で不変かどうか
        F1 = 2 if (N % 4) <= 1 else 0
        # メインの式
        ans = (8*fact[N]
               - 8*I[N]
               - 4*F2[N]
               + 6*J[N]
               - 2*F1) % M
        out.append(str(ans))
    sys.stdout.write("\n".join(out))

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