102716: [AtCoder]ABC271 G - Access Counter

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

Problem Statement

Takahashi has decided to put a web counter on his webpage.
The accesses to his webpage are described as follows:

  • For $i=0,1,2,\ldots,23$, there is a possible access at $i$ o'clock every day:
    • If $c_i=$T, Takahashi accesses the webpage with a probability of $X$ percent.
    • If $c_i=$A, Aoki accesses the webpage with a probability of $Y$ percent.
    • Whether or not Takahashi or Aoki accesses the webpage is determined independently every time.
  • There is no other access.

Also, Takahashi believes it is preferable that the $N$-th access since the counter is put is not made by Takahashi himself.

If Takahashi puts the counter right before $0$ o'clock of one day, find the probability, modulo $998244353$, that the $N$-th access is made by Aoki.

Notes

We can prove that the sought probability is always a finite rational number. Moreover, under the constraints of this problem, when the value is represented as $\frac{P}{Q}$ with two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

  • $1 \leq N \leq 10^{18}$
  • $1 \leq X,Y \leq 99$
  • $c_i$ is T or A.
  • $N$, $X$, and $Y$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $X$ $Y$
$c_0 c_1 \ldots c_{23}$

Output

Print the answer.

Sample Input 1

1 50 50
ATATATATATATATATATATATAT

Sample Output 1

665496236

The $1$-st access since Takahashi puts the web counter is made by Aoki with a probability of $\frac{2}{3}$.

Sample Input 2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT

Sample Output 2

0

There is no access by Aoki.

Sample Input 3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT

Sample Output 3

744124544

Input

题意翻译

【题目翻译】 给定 $24$ 个时间点，每个时间点有可能有两种指令 如果指令是 `T`，则高桥有 $x\%$ 的概率登录洛谷。 如果指令是 `A`，则青木有 $y\%$ 的概率登录洛谷。 操作是依次进行的。求洛谷第 $n$ 次被登录是由青木操作的概率。 答案对 $998244353$ 取模。 【输入格式】 第一行三个数 $n,x,y$。 接下来有 24 个操作，每个操作只会有 `T` 或 `A`。 【输出格式】 求洛谷第 $n$ 次被登录是由青木操作的概率。 Translated by @cc0000

Output

分数：$600$分 部分 问题描述 高桥决定在他的网页上放置一个网络计数器。 对他网页的访问如下描述： - 对于$i=0,1,2,\ldots,23$，每天都有可能在$i$点进行访问： - 如果$c_i=$`T`，高桥访问网页的概率为$X$%。 - 如果$c_i=$`A`，青木访问网页的概率为$Y$%。 - 高桥或青木是否访问网页每次都是独立决定的。 - 除此之外没有其他访问。 此外，高桥认为计数器放置后第$N$次访问不是他自己进行的更好。 如果高桥在一天的$0$点**刚好**放置计数器，求第$N$次访问是由青木进行的概率，对$998244353$取模。 部分 注释 我们可以证明所求概率总是有限的有理数。此外，在本问题的约束下，当该值表示为$\frac{P}{Q}$，其中$P$和$Q$是互质的整数时，我们可以证明存在一个整数$R$，使得$R \times Q \equiv P\pmod{998244353}$且$0 \leq R \lt 998244353$。找到这个$R$。 部分 约束 - $1 \leq N \leq 10^{18}$ - $1 \leq X,Y \leq 99$ - $c_i$是`T`或`A`。 - $N$，$X$和$Y$是整数。 部分 输入 输入按照以下格式从标准输入给出： $N$ $X$ $Y$ $c_0 c_1 \ldots c_{23}$ 部分 输出 打印答案。 部分 样例输入 1 ``` 1 50 50 ATATATATATATATATATATATAT ``` 部分 样例输出 1 ``` 665496236 ``` 计数器放置后，高桥的第$1$次访问由青木进行的概率为$\frac{2}{3}$。 部分 样例输入 2 ``` 271 95 1 TTTTTTTTTTTTTTTTTTTTTTTT ``` 部分 样例输出 2 ``` 0 ``` 没有青木的访问。 部分 样例输入 3 ``` 10000000000000000 62 20 ATAATTATATTTAAAATATTATAT ``` 部分 样例输出 3 ``` 744124544 ```

Source/Category

加入题单

算法标签：