No.8119 Didn't Make It in Time >_<;
I'm sorry >_<;
I didn't finish creating a problem in time >_<;
Instead, I ported one of my past problems to yukicoder, so please forgive me with this >_<;
I worked in a big hurry, so there may be configuration mistakes >_<;
Problem Statement
There are $N + 1$ squares arranged in a row, numbered $0, 1, \ldots, N$ in order.
You are given a string $S = S_0 S_1 \cdots S_N$ of length $N + 1$ consisting only of o and x. If $S_i$ is o, there is no stone on square $i$; if $S_i$ is x, there is a stone on square $i$. It is guaranteed that there are no stones on square $0$ and square $N$.
Takahashi, who is good at the triple jump, starts at square $0$ and aims to stop exactly on square $N$ by repeating the following operation any number of times, possibly $0$.
- Choose one positive integer $k$.
- Let square $i$ be the current position. If square $i + 2 k$ exists and has no stone on it, move to square $i + 2 k$. Otherwise, he falls over.
- Let square $i$ be the current position. If square $i + 3 k$ exists and has no stone on it, move to square $i + 3 k$. Otherwise, he falls over.
- Let square $i$ be the current position. If square $i + 5 k$ exists and has no stone on it, move to square $i + 5 k$. Otherwise, he falls over.
The steps of an operation are performed consecutively and cannot be interrupted.
Find the number of ways for Takahashi to move from square $0$ to square $N$ without falling over. Since the answer can be very large, output it modulo $998244353$.
Constraints
- $1 \leq N \leq 1.4 \times 10^5$
- $N$ is an integer
- $S$ is a string of length $N + 1$ consisting only of
oandx - $S_0 =$
o, $S_N =$o
Input
The input is given from Standard Input in the following format.
$N$ $S$
Output
Output the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
20 oxooxoooooooooooooxxo
Output
1
If he chooses $k = 1$ in the first operation:
- The current position is square $0$. Square $0 + 2 \times 1 = 2$ exists, and since $S_2 =$
othere is no stone on it, so he moves to square $2$. - The current position is square $2$. Square $2 + 3 \times 1 = 5$ exists, and since $S_5 =$
othere is no stone on it, so he moves to square $5$. - The current position is square $5$. Square $5 + 5 \times 1 = 10$ exists, and since $S_{10} =$
othere is no stone on it, so he moves to square $10$.
Thus he can move to square $10$. If he then chooses $k = 1$ in the next operation:
- The current position is square $10$. Square $10 + 2 \times 1 = 12$ exists, and since $S_{12} =$
othere is no stone on it, so he moves to square $12$. - The current position is square $12$. Square $12 + 3 \times 1 = 15$ exists, and since $S_{15} =$
othere is no stone on it, so he moves to square $15$. - The current position is square $15$. Square $15 + 5 \times 1 = 20$ exists, and since $S_{20} =$
othere is no stone on it, so he moves to square $20$.
Thus he can move to square $N = 20$.
On the other hand, if he chooses $k = 2$ in the first operation:
- The current position is square $0$. Square $0 + 2 \times 2 = 4$ exists, but since $S_4 =$
xthere is a stone on it, so he falls over.
Thus he falls over.
Also, if he chooses $k = 10$ in the first operation:
- The current position is square $0$. Square $0 + 2 \times 10 = 20$ exists, and since $S_{20} =$
othere is no stone on it, so he moves to square $20$. - The current position is square $20$. Square $20 + 3 \times 10 = 50$ does not exist, so he falls over.
Thus he falls over (the operation cannot be interrupted).
The only way to move without falling over is the one described first, so there is $1$ way; output $1$, which is $1$ modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。