D - Progressive Jackpot
Flavor
2
s
1024
MB
600
点
問題文
問題のストーリー
メダルゲームで、「プログレッシブジャックポット」という概念があります。これは、「ある大きい当たりを用意しておいて、外れるたびに少しずつ当たり額を上げ、当たったときにその時の当たり額を払い出し、当たり額を初期化する」といったものです。
当たり額の初期値が $A$ 、上限が $B$ 、外れた時に上がる額が $C$ としたとき、 $N$ 回の抽選で当たったか外れたかが一部のみ与えられるので、残りを当たりか外れで埋める全ての方法に対し、当たり額の総和を $998244353$ で割った余りを求めてください。
厳密な問題文
長さ $N$ の文字列 $S$ と，正の整数 $A,B,C$ が与えられます。
$S$ に含まれる ? の個数を $Q$ として、その全ての ? をそれぞれ o または x に置き換える $2^Q$ 通りの方法に対し、次の操作を終えた時の $ans$ の総和を求め、 $998244353$ で割った余りを出力してください。
- 変数 $ans = 0, J = A$ を用意する。
- $i = 1, 2, \cdots , N$ について、順に以下の操作を行う。
- $S_i$ =
oならば、$ans \leftarrow ans + J , J \leftarrow A$ - $S_i$ =
xならば、$J \leftarrow \min(J+C, B)$
- $S_i$ =
制約
- $N,A,B,C$ は整数
- $|S|=N$
- $S$ は
o,x,?からなる文字列 - $1\leq N\leq 2×10^5$
- $1\leq A\leq B\leq 9×10^8$
- $1\leq C\leq 9×10^8$
入力
入力は以下の形式で与えられる。
$N$
$S$
$A$ $B$ $C$
出力
$S$ の?をそれぞれoまたはxに置き換える全ての方法に対する、操作を終えた時の $ans$ の総和を $998244353$ で割った余りを出力せよ。
入力例 1
5
x??ox
1000 1299 100
出力例 1
8799
?を全て置き換えた後の文字列としては、xooox,xoxox,xxoox,xxxoxがあります。
それぞれの最終的な $ans$ は、 $1100+1000+1000=3100,1100+1100=2200,1200+1000=2200,1299$です。これらの総和である $8799$ が答えとなります。
入力例 2
10
xxxxxxxxxx
100000 100000 999999
出力例 2
0
oは現れません。
入力例 3
20
o?oxx?x??oo?oxxx?o??
4000000 9999999 2000000
出力例 3
296578642
$998244353$ で割った余りを出力してください。