お知らせ (2026/01/24)

この問題は, 現在, Writer 解と Tester 解で求めていた値が, 本来求めるべきではなかったものであることが確認されています.

そのため, この問題は不備あり問題とさせていただきます.

申し訳ありませんでした.

問題ヴィジュアル

問題文

正の整数 $N$ と以下が与えられる.

• G, B からなる, 添字が $1$ から始まる, 長さ $N$ の文字列 $S$.
• 添字が $0$ から始まる, 長さ $(N+1)$ の非負整数列 $W$

$Q$ 個のクエリが与えられる. クエリは以下の $3$ 個のタイプのうちのいずれかである.

• Type I: 整数 $l, r~(1 \leq l \leq r \leq N)$ が与えられる. $S$ の $l$ 文字目から $r$ 文字目について, G, B を交代させる. 厳密には $l \leq i \leq r$ を満たす全ての整数 $i$ について, $1$ 回ずつ以下のように $S$ を操作する.
  • $S$ の $i$ 文字目が G だった場合, $S$ の $i$ 文字目を B に変更する.
  • $S$ の $i$ 文字目が B だった場合, $S$ の $i$ 文字目を G に変更する.
• Type II: 整数 $l, r~(0 \leq l \leq r \leq N), a$ が与えられる. $(r-l+1)$ 個の整数 $W_l, \dots, W_r$ に $a$ を加算する. なお, このクエリの実行後について, 以下が保証されている.
  • $W_l, \dots, W_r$ は全て非負整数である.
  • $W_0 > 0$.
  • $\sum_{i=0}^N W_i < 998244353$.
• Type III: 整数 $K$ 及び, $(K+1)$ 個の整数 $v, u_1, \dots, u_K$ が 2行に渡って与えられる. このとき, このクエリが与えられた時点での $N, S, W$ 及び, クエリで与えられた $K, v, u_1, \dots, u_K$ に対して, 以下で定義される問 Go or Back!! に答えよ.

  Go or Back!!

  無向グラフ $G$ がある. この $G$ は最初, $1$ 頂点 $0$ 辺である. この唯一の頂点を頂点 $0$ ということにする. チェリーちゃんは最初, 頂点 $0$ にいる.

  チェリーちゃんはこれから $N$ 回の行動を行う. $i~(1 \leq i \leq N)$ 回目の行動は以下を (1), (2) の順に行う. ただし, $S$ の $i$ 文字目を $S_i$ と書く.

  • (1) チェリーちゃんが今いる頂点の番号を $x$ とする. $G$ に $1$ 個の頂点, 頂点 $i$ を加える. その後, $G$ に頂点 $x$ と頂点 $i$ を結ぶ無向辺を $1$ 本加える.
  • (2) $S_i$ によって以下のように行動する.
    • $S_i = $ G のとき, 頂点 $i$ に移動する.
    • $S_i = $ B のとき, 頂点 $i$ に移動する. その後, 整数 $j$ を $0$ 以上 $i$ 以下の $(i+1)$ 個の整数から $W_j$ に比例する確率で選び, 選んだ $j$ に対して, 頂点 $j$ に移動する.
      • 厳密には, $0$ 以上 $i$ 以下の整数として $j$ が選ばれる確率は, $\dfrac{W_j}{W_0 + W_1 + \dots + W_i}$ である.

  ただし, (2) の $S_i =$ B である場合における頂点を選ぶ方法は独立である.

  チェリーちゃんが $N$ 回の行動を終えた後の $G$ は $(N+1)$ 頂点の木であることが保証される.

  このとき, $k = 0, 1, 2, \dots, K$ のそれぞれに対して, 以下が成立する確率を $P_k$ としたとき, $P_k \pmod{998244353}$ を求めよ.

  • $G$ を頂点 $0$ を根とする根付き木とみたとき, $K$ 個の頂点 $u_1, \dots, u_K$ のうち, ちょうど $k$ 個が頂点 $v$ の子孫 (頂点 $v$ 自身は頂点 $v$ の子孫であるとする) になる.

注記

この問題の制約下では, Go or Back!! の解答におけるそれぞれの $P_k$ において, 以下を満たすような整数の組 $(\alpha, \beta)$ が存在することが証明できる.

• $\beta$ は $998244353$ の倍数ではない.
• $\beta \times P_k = \alpha$.

この条件を満たすような整数の組 $(\alpha, \beta)$ に対して, $$\beta \times \gamma \equiv \alpha \pmod{998244353}$$ となる $0$ 以上 $998244353$ 未満の整数 $\gamma$ が唯一存在する. この整数 $\gamma$ を用いて, $P_k \pmod{998244353} := \gamma$ と定義する.

なお, 条件を満たすような整数の組 $(\alpha, \beta)$ は数多に考えられるが, $\gamma$ は $\alpha, \beta$ の取り方に依らず, $P_k$ のみによって決まることが証明できる.

制約

• $1 \leq N \leq 2 \times 10^5$.
• $S$ は G, B からなる長さ $N$ の文字列.
• $0 \leq W_i \quad (0 \leq i \leq N)$.
• $W_0 > 0$.
• $\displaystyle \sum_{i=0}^N W_i < 998244353$.
• $1 \leq Q \leq 2 \times 10^5$.
• クエリに関する性質
  • Type I
    • $1 \leq l \leq r \leq N$.
  • Type II
    • $0 \leq l \leq r \leq N$.
    • このクエリの実行後について, 以下が成り立っている.
      • $W_l, \dots, W_r$ は非負整数である.
      • $W_0 > 0$.
      • $\sum_{i=0}^N W_i < 998244353$.
  • Type III
    • $0 \leq v \leq N$.
    • $1 \leq K \leq N + 1$.
    • $0 \leq u_1 < u_2 < \dots < u_K \leq N$.
• テストファイルに関する制約
  • Type III において与えられる $K$ の総和は $4 \times 10^5$ 以下である.
• 入力で与えられる数は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.

$N$ $Q$
$S$
$W_0$ $W_1$ $\cdots$ $W_N$
$\textrm{Query}_1$
$\textrm{Query}_2$
$\vdots$
$\textrm{Query}_Q$

各クエリ $\textrm{Query}_q$ は以下の形式で与えられる.

• Type I

  $1$ $l$ $r$

• Type II

  $2$ $l$ $r$ $a$

• Type III (入力が $2$ 行になることに注意せよ!!)

  $3$ $v$ $K$
  $u_1$ $\dots$ $u_K$

出力

出力は, Type III のクエリの数を $Q_3$ としたとき, $Q_3$ 行からなる.

第 $r~(1 \leq r \leq Q_3)$ 行目には, $r$ 回目の Type III のクエリに対する $P_0 \pmod{998244353}, P_1 \pmod{998244353}, \dots, P_K \pmod{998244353}$ をこの順に空白区切りで出力せよ.

最後に改行を忘れないこと.

サンプル

5 4
GBBGG
7 2 5 3 4 6
3 1 3
2 3 5
2 1 2 -1
1 2 5
3 2 4
0 1 2 5

0 748683265 499122177 748683265
0 840626824 157617530 0 0

27 4
GBBBBBBBBBBBBBBBBGGGGBGGGGG
20240221 20050928 19970104 19981114 19980215 20010129 19990417 20000418 19991012 20021219 20020323 19981021 20010829 20020112 19991013 20010710 20000102 20020113 20060109 20040725 20050707 20050412 20030217 20061108 20060509 20040818 20050215 20050122
3 1 28
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
2 2 17 -200000
2 22 22 -200000
3 1 28
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

0 0 222988788 771769147 992116430 710638604 457685736 692110246 611753846 627562333 676906014 653592675 487428586 980604359 696548956 58536970 520775465 988181969 248027971 769018906 322625600 314143540 950198154 997357843 689168976 582264942 62212162 887691431 0
0 0 155273704 671270277 521295779 361253626 655040713 211805211 873728974 641978190 429760573 563027688 632727160 595596749 82203229 601652105 441511828 336327499 544567300 778057437 840394959 332445457 264024640 263262986 995391962 592085902 410020362 182472280 0