問題一覧 > 通常問題

No.1873 Bracket Swapping

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : ytqm3 / テスター : ぷら shiomusubi496
7 ProblemId : 7091 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-03 13:58:51

問題文

正規括弧列 SS と非負整数 KK が与えられます。 SS に対して次の操作を KK 回する方法のうち、操作後の SS が正規括弧列になるものの個数を 998244353998244353 で割った余りを求めてください。

  • 1≤i<j≤∣S∣1 \le i < j \le |S| を満たす整数対 (i,j)(i, j) を選ぶ。 SS の ii 文字目と jj 文字目を交換する。

ただし、ある整数 l (1≤l≤K)l\ (1 \le l \le K) が存在して ll 回目に選んだ (i,j)(i,j) が異なるとき、またその時に限り 22 つの操作の方法を異なるとみなします。


正規括弧列の定義 (クリックで展開します)

以下のいずれかの条件を満たすような文字列を正規括弧列と定義します。

  • 空文字列
  • ある正規括弧列 AA が存在して、 (,A,,A,) をこの順に連結した文字列
  • ある空でない正規括弧列 A,BA, B が存在して、 A,BA, B をこの順に連結した文字列

入力

SS
KK
  • SS は正規括弧列
  • 2≤∣S∣≤2002 \le |S| \le 200
  • 0≤K≤1090 \le K \le 10^9

出力

答えを出力してください。

サンプル

サンプル1
入力
(())
1
出力
3

11 度目の操作で (i,j)=(1,2),(2,3),(3,4)(i,j)=(1,2),(2,3),(3,4) を選んだ時条件を満たします。

サンプル2
入力
()
100
出力
1

サンプル3
入力
(()(()(())()))
924844033
出力
392727613

998244353998244353 で割った余りを求めることをお忘れなく。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。