結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:25:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 826 ms / 2,000 ms |
コード長 | 747 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 178,620 KB |
最終ジャッジ日時 | 2025-04-11 22:25:54 |
合計ジャッジ時間 | 9,537 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
import sys sys.setrecursionlimit(10**7) from functools import cache MOD=998244353 @cache def factorial(d): if d == 0 or d == 1: return 1 else: return (d * factorial(d - 1))%MOD for i in range(10**6): factorial(i) def repeatedsquare(a,b): rep=[0]*62 rep[0]=a for i in range(1,62): rep[i]=(rep[i-1]*rep[i-1])%MOD ret=1 for i in range(62): if (b>>i)&1: ret=(ret*rep[i])%MOD return ret N=int(input()) n=N//2 S=input() if S[0]!=S[1]: type=1 else: type=0 if type==1: ans = 1 for i in range(n): ans=(ans*2)%MOD else: ans = 0 for r in range(0, n+1): x=factorial(n)*repeatedsquare(factorial(n-r), (MOD-2))*repeatedsquare(factorial(r),(MOD-2))%MOD ans = (ans + x*x)%MOD print(ans)