問題一覧 > ネタ問題

No.8119 Didn't Make It in Time >_<;

レベル : / 実行時間制限 : 1ケース 0.020秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 14
作問者 : ecottea / テスター : 👑 獅子座じゃない人
お気に入りにしたユーザー ProblemId : 11838 / 自分の提出
問題文最終更新日: 2025-03-26 14:32:34
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 April Fool Contest 2025 (順位表) の他の問題:

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 o and x
  • $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 =$ o there 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 =$ o there 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} =$ o there 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} =$ o there 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} =$ o there 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} =$ o there 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 =$ x there 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} =$ o there 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もしくは右上の雲マークをクリックしてアカウントを作成してください。