結果
問題 | No.3099 Parentheses Decomposition |
ユーザー |
![]() |
提出日時 | 2025-04-11 21:50:34 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 464 ms / 2,000 ms |
コード長 | 535 bytes |
コンパイル時間 | 15,440 ms |
コンパイル使用メモリ | 246,648 KB |
実行使用メモリ | 8,024 KB |
最終ジャッジ日時 | 2025-04-11 21:50:54 |
合計ジャッジ時間 | 19,194 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
package main import . "fmt" import . "math/big" const M=998244353 func main() { var n int var s string Scan(&n,&s) if s[1]==')' { Println(new(Int).Exp(NewInt(2),NewInt(int64(n/2)),NewInt(M))) return } c:=make([]int,n/2+1) c[0]=1 for i:=range c[1:] { c[i+1]=c[i]*(i+1)%M } d:=make([]int,n/2+1) d[n/2]=int(new(Int).ModInverse(NewInt(int64(c[n/2])),NewInt(M)).Int64()) for i:=n/2;i>0;i-- { d[i-1]=d[i]*i%M } var ans int for i:=0;i<=n/2;i++ { x:=c[n/2]*d[i]%M*d[n/2-i]%M ans+=x*x%M ans%=M } Println(ans) }