問題一覧 > 通常問題

No.2106 Wild Cacco

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
5 ProblemId : 8329 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-08 17:45:10

問題文

(,),? のみからなる文字列 $t$ が次の条件を満たすとき、$t$ は 良い文字列 であるとします。

  • $t$ における ? のそれぞれを (,) のいずれかに適切に置き換えることで、正しい括弧列にできる。

例えば、$t=$ ?(?)? の置き換えにより (()) とできるため、良い文字列です。
同様に、$t=$ ???? や $t=$ ()()() も良い文字列です(必ずしも $t$ に ? が含まれている必要はありません)。
一方、$t=$ )???? をどのように置き換えても正しい括弧列にはならないため、良い文字列ではありません。

(,),?,. のみからなる文字列 $s$ が与えられます。
$s$ における . のそれぞれを (,),? のいずれかに置き換えることで得られるような良い文字列は何通りあるでしょうか。
答えは非常に大きくなることがあるので、$998244353$ で割った余りを求めてください。

補足

正しい括弧列とは次のように定義されます。
  1. 空文字列は正しい括弧列である。
  2. 文字列 $A$ が正しい括弧列であるとき、($,A,$ ) をこの順に並べた文字列も正しい括弧列である。
  3. 空でない文字列 $A,B$ が正しい括弧列であるとき、$A,B$ をこの順に並べた文字列も正しい括弧列である。
  4. 上記1~3のいずれかの条件を満たす文字列のみが正しい括弧列である。

制約

  • $s$ は (,),?,. のみからなる文字列である。
  • $1\le |s|\le 4000$

入力

入力は以下の形式で標準入力から与えられます。

$s$

出力

$s$ における . のそれぞれを (,),? のいずれかに置き換えることで得られるような良い文字列の数を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
..
出力
4

(), ?), (?, ?? の $4$ 通りです。

サンプル2
入力
((.?
出力
2

(()?, ((?? の $2$ 通りです。

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

サンプル4
入力
((()
出力
0

サンプル5
入力
(...)?..?.
出力
358

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