問題一覧 > 通常問題

No.2524 Stripes

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : Shirotsume / テスター : MasKoaTS fky_
お気に入りにしたユーザー ProblemId : 10132 / 自分の提出
問題文最終更新日: 2023-10-27 18:45:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 410 (順位表) の他の問題:

Problem Statement

There are $N$ balls. The integer $i$ is written on the $i$-th ball.

Each ball is painted in exactly one of two colors, red or blue, and this information is represented by a string $S$. Specifically, if the $i$-th character of $S$ is R, the $i$-th ball is painted red, and if it is B, it is painted blue.

For $i = 1, \dots, N$ in this order, solve the following problem.

  • Find the number, modulo $998244353$, of ways to choose $i$ balls from the $N$ balls such that, when the chosen balls are arranged in a row in ascending order of the integers written on them, the colors alternate, that is, no two adjacent balls have the same color.

Constraints

  • $N$ is an integer
  • $1 \leq N \leq 10^5$
  • $S$ is a string of length $N$ consisting only of R and B

Input

The input is given from standard input. Each test case is given in the following format.

$N$
$S$

Output

Output $N$ lines. On the $k$-th line, output the answer for $i = k$.

Sample

Sample 1
Input
4
RRBR
Output
4
3
2
0

$i = 1$ : There are $4$ ways to choose $1$ ball from the $4$ balls. All of them satisfy the condition in the problem statement.

$i = 2$ : There are $6$ ways to choose $2$ balls from the $4$ balls. Among them, the $3$ ways $(1,3),(2,3),(3,4)$ satisfy the condition.

Choosing $(1,2)$ does not satisfy the condition, because when the balls are arranged in ascending order of their numbers, the colors are RR, which do not alternate.

$i = 3$ : The $2$ ways $(1, 3, 4), (2, 3, 4)$ satisfy the condition.

$i = 4$ : No way satisfies the condition.

Sample 2
Input
2
BB
Output
2
0
Sample 3
Input
10
RBRRBBRBRR
Output
10
24
40
35
34
12
8
0
0
0

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