시간 제한메모리 제한제출정답맞힌 사람정답 비율
15 초 2048 MB888100.000%

문제

The ICPC logo has three colors: blue, yellow, and red. The NAC volunteers have just inflated a huge number of balloons in these colors and arranged them in a line. They next need to sort the balloons by color before they can give them out to contestants.

Unfortunately, due to the Orlando heat, the balloons begin to randomly pop: each second, a random remaining balloon pops (and the volunteers remove the debris from the line). This isn't all bad: maybe if the NAC volunteers wait long enough, the balloons will become sorted by chance? Compute the expected number of seconds until the first time that all blue balloons come before all yellow and red balloons, and all yellow balloons come before all red balloons. (These conditions are satisfied even if they are vacuously true: for example, if there are no blue balloons at all remaining, then it is true that all blue balloons come before all yellow and red balloons.)

입력

The input has one line: a string $s$ ($1\le |s|\le 2\cdot 10^5$) where each character is one of $B$, $Y$, or $R$ representing blue, yellow, and red respectively ---the colors of the initial balloons in the line.

출력

Print the expected number of seconds that elapse before the first time that all blue balloons come before all yellow and red balloons, and all yellow balloons come before all red balloons. Since this number might not be an integer, print it modulo $998\, 244\, 353$.

Formally, let $p = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are non-negative integers and $b \not \equiv 0 \pmod{p}$. Print the integer $x$ with $0 \leq x < p$ and $x \equiv a \cdot b^{-1} \bmod p$.

예제 입력 1

RYBB

예제 출력 1

831870297

In Sample Input 1, the expected time until the balloon colors first become sorted in the correct order is $\frac {17}{6} = 2\cdot \frac{1}{6} + 3 \cdot \frac{5}{6}$ seconds: the only way for the balloon colors to be sorted correctly after $2$ seconds is if the first two balloons to pop are the yellow and red balloon (in either order). The probability that these balloons pop before either blue balloon is $\frac{1}{6}$. Otherwise (with probability $\frac{5}{6}$) the balloon colors will automatically be sorted after $3$ seconds, when there is only one balloon left. Since $6^{-1} \equiv 166\,374\,059\pmod {p}$, the answer is $17\cdot 166\,374\,059\equiv 831\,870\,297\pmod{p}$.

예제 입력 2

YRBBR

예제 출력 2

598946615

출처

ICPC > Regionals > North America > North America Championship > North America Championship 2025 J번

  • 문제를 만든 사람: Misha Ivkov