結果
問題 | No.3043 括弧列の数え上げ |
ユーザー |
![]() |
提出日時 | 2025-02-28 22:49:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 736 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 108,084 KB |
最終ジャッジ日時 | 2025-02-28 22:49:31 |
合計ジャッジ時間 | 6,698 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
N=int(input()) dp=[[0 for _ in range(N)] for _ in range(N+1)] dp[0][0]=1 p=998244353 for i in range(N): for j in range(N): if j!=N-1: dp[i+1][j+1]+=dp[i][j] dp[i+1][j+1]%=p if j!=0: dp[i+1][j-1]+=dp[i][j] dp[i+1][j-1]%=p #print(dp) 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 if a>=0 and b>=0 and c>=0 and d>=0: #print(f'i={i} j={j} a={a} b={b} c={c} d={d}') ans+=dp[a+b][b-a]*dp[c+d][d-c]*(j-1) ans%=p print(ans)