問題一覧 > 通常問題

No.2524 Stripes

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : ShirotsumeShirotsume / テスター : MasKoaTSMasKoaTS fky_fky_
3 ProblemId : 10132 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-27 18:45:24

問題文

ボールが $N$ 個あります。$i$ 番目のボールには整数 $i$ が書かれています。

また、それぞれのボールは赤か青のどちらか一方の色で塗られており、その情報は文字列 $S$ で表されます。具体的には、$S$ の $i$ 文字目が R ならば $i$ 番目のボールは赤、 B ならば青で塗られています。

$i = 1, \dots, N$ の順に、次の問題を解いてください。

  • $N$ 個のボールから $i$ 個選ぶ方法であって、選ばれたボールを書かれた整数の昇順に横一列に並べたとき色が交互に並ぶ、すなわち同じ色のボールが隣り合わない選び方の数を $998244353$ で割った余りを求めよ。

制約

  • $N$ は整数
  • $1 \leq N \leq 10^5$
  • $S$ は R または B のみからなる長さ $N$ の文字列

入力

入力は標準入力から与えられる。テストケースは以下の形式で与えられる。

$N$
$S$

出力

$N$ 行にわたって出力せよ。$k$ 行目には、$i = k$ のときの答えを出力せよ。

サンプル

サンプル1
入力
4
RRBR
出力
4
3
2
0

$i = 1$ : $4$ 個のボールから $1$ 個選ぶ方法は $4$ 通りあります。これらはすべて問題文の条件を満たします。

$i = 2$ : $4$ 個のボールから $2$ つ選ぶ方法は $6$ 通りあります。このうち、$(1,3),(2,3),(3,4)$ の $3$ つの方法が条件を満たします。

$(1,2)$ を選ぶ方法は、ボールを数の昇順に並べると色が RR となり、色が交互に並んでいないため条件を満たしません。

$i = 3$ : $(1, 3, 4), (2, 3, 4)$ の $2$ つの方法が条件を満たします。

$i = 4$ : 条件を満たす方法はありません。

サンプル2
入力
2
BB
出力
2
0
サンプル3
入力
10
RBRRBBRBRR
出力
10
24
40
35
34
12
8
0
0
0

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