問題一覧 > 通常問題

No.1677 mæx

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : stoqstoq / テスター : akakimidoriakakimidori saksak
15 ProblemId : 6497 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-07 20:42:05

問題文

$0,1,2$ と関数 ${\rm max,mex}$ から成る正しい式 $S$ があります。

ここでの正しい式、及びその式の値の定義は次の通りです。

  • 数字0,1,2は正しい式であり、その値は(数としての)その数字である。
  • $A,B$ が正しい式のとき、max($A$,$B$)は正しい式であり、その値は $A,B$ の値のうちの大きい方である。
  • $A,B$ が正しい式のとき、mex($A$,$B$)は正しい式であり、その値は $A,B$ の値のいずれとも一致しない最小の非負整数である。
  • 正しい式は上記のものに限る。

例えばmex(max(1,2),max(0,0)) は正しい式で、その値は ${\rm mex}({\rm max}(1,2),{\rm max}(0,0)) = {\rm mex}(2,0) = 1$ です。

いたずら好きのyukiさんは $S$ に含まれる 0,1,2,a,e のうち、0文字以上を?に変えてしまいました。

変更後の $S$ と整数 $K$ が与えられるので、式の値が $K$ であるような元の正しい式としてあり得るものは何通りかを求めてください。

答えは非常に大きくなることがあるため、 $998244353$ で割った余りを出力してください。

入力

$S$
$K$

  • $1 \leq |S| \leq 2 \times 10^5$
  • $S$ は問題文中の正しい式の0,1,2,a,e のうち、0文字以上を?に変更した文字列
  • $K = 0,1,2$

出力

式の値が $K$ であるような元の正しい式としてあり得るものの個数を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
m?x(1,2)
0
出力
1

この場合、条件を満たす正しい式は mex(1,2) のみです。

サンプル2
入力
max(?,mex(0,?))
2
出力
5

サンプル3
入力
m?x(m?x(m?x(?,?),m?x(?,?)),m?x(m?x(?,?),m?x(?,?)))
1
出力
250269

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

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