結果

問題 No.3043 括弧列の数え上げ
コンテスト
ユーザー nikoro256
提出日時 2025-02-28 22:41:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 922 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 77,024 KB
最終ジャッジ日時 2025-02-28 22:41:29
合計ジャッジ時間 6,349 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p=998244353
N = 3000  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用S
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

N=int(input())
ans=0
for i in range(1,N):
    for j in range(1,N):
        if (i-j)%2==1 or (N-1-i-j+1)%2==1:
            continue
        #i個目でjステージ上がっている
        a=(i-j)//2
        b=(i+j)//2
        c=(N-1-i-j+1)//2
        d=(N-1-i+j-1)//2
        #print(f'i={i} j={j} a={a} b={b} c={c} d={d}')
        if a>=0 and b>=0 and c>=0 and d>=0:
            ans+=cmb(a+b,a,p)*cmb(c+d,c,p)*(j-1)
            ans%=p
print(ans)
0