No.2524 Stripes

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 :

Shirotsume / テスター :

MasKoaTS

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$ 
 $S$

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

4
RRBR

$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
BB

2
0

10
RBRRBBRBRR

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