結果

問題 No.3123 Inversion
コンテスト
ユーザー Nzt3
提出日時 2025-04-10 02:12:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,603 ms / 10,000 ms
コード長 1,058 bytes
コンパイル時間 1,143 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 273,108 KB
最終ジャッジ日時 2025-04-18 00:22:58
合計ジャッジ時間 53,267 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

T, M = map(int, input().split())
MAX_N = 5*10**6+10
rot4 = [0]*MAX_N
rot2 = [0]*MAX_N
rot2_sym = [0]*MAX_N
sym = [0]*MAX_N
fact = [0]*MAX_N

rot4[4] = 2
for i in range(8, MAX_N, 4):
    rot4[i] = rot4[i-4]*(i-2) % M
for i in range(5, MAX_N, 4):
    rot4[i] = rot4[i-1]

rot2_sym[2] = 2
rot2_sym[4] = 6
for i in range(6, MAX_N, 2):
    rot2_sym[i] = (2*rot2_sym[i-2]+(i-2)*rot2_sym[i-4]) % M
for i in range(3, MAX_N, 2):
    rot2_sym[i] = rot2_sym[i-1]

rot2[2] = 2
for i in range(4, MAX_N, 2):
    rot2[i] = i*rot2[i-2] % M
for i in range(3, MAX_N, 2):
    rot2[i] = rot2[i-1]

sym[1] = 1
sym[2] = 2
for i in range(3, MAX_N):
    sym[i] = (sym[i-1]+(i-1)*sym[i-2]) % M

fact[0] = 1
for i in range(1, MAX_N):
    fact[i] = i*fact[i-1] % M

for _ in range(T):
    N = int(input())
    if N == 1:
        print(1 % M)
        continue
    c2 = rot4[N]
    c3 = rot2_sym[N]
    c4 = (rot2[N]-rot2_sym[N]-rot4[N]) % M
    c5 = (sym[N]-rot2_sym[N]) % M
    c6 = c5
    c7 = (fact[N]-c2-c3-c4-c5-c6) % M
    ans = (c2*2+c3*2+c4*4+c5*4+c6*4+c7*8) % M
    print(ans)
0