結果

問題 No.3099 Parentheses Decomposition
ユーザー ID 21712
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
}
0