No.8119 間に合いませんでした＞＜；
タグ : / 解いたユーザー数 14
作問者 :
ecottea
/ テスター :
👑 ごめんなさい＞＜；
問題の作成が間に合いませんでした＞＜；
代わりに過去作を yukicoder に移植したのでこれで許してください＞＜；
大慌てで作業したので設定ミスしてるかもしれません＞＜；
問題文
$N + 1$ 個のマスが一列に並んでおり，順に $0, 1, \ldots, N$ の番号が付けられています．
また o，x のみからなる長さ $N + 1$ の文字列 $S = S_0 S_1 \cdots S_N$ が与えられ，$S_i$ が o のときマス $i$ に石がないことを，$S_i$ が x のときマス $i$ に石があることを表します．マス $0$ とマス $N$ には石がないことが保証されます．
三段跳びが得意な高橋君はマス $0$ からスタートし，以下の操作を $0$ 回以上好きな回数繰り返すことでマス $N$ でちょうど停止することを目指します．
- 正整数 $k$ を 1 つ選ぶ．
- 現在位置をマス $i$ とする．マス $i + 2 k$ が存在しそこに石がないならばマス $i + 2 k$ に移動する．さもなくば転倒する．
- 現在位置をマス $i$ とする．マス $i + 3 k$ が存在しそこに石がないならばマス $i + 3 k$ に移動する．さもなくば転倒する．
- 現在位置をマス $i$ とする．マス $i + 5 k$ が存在しそこに石がないならばマス $i + 5 k$ に移動する．さもなくば転倒する．
なお操作は続けて行われ，中断することはできません．
高橋君が転倒することなくマス $0$ からマス $N$ に移動する方法が何通りあるか求めてください． 答えは非常に大きくなることがあるので，答えを $998244353$ で割った余りを出力してください．
制約
- $1 \leq N \leq 1.4 \times 10^5$
- $N$ は整数
- $S$ は
o，xのみからなる長さ $N + 1$ の文字列 - $S_0 =$
o，$S_N =$o
入力
入力は以下の形式で標準入力から与えられます．
$N$ $S$
出力
答えを $998244353$ で割った余りを出力してください．最後に改行してください．
サンプル
サンプル1
入力
20 oxooxoooooooooooooxxo
出力
1
最初の操作で $k = 1$ と選ぶと
- 現在位置はマス $0$ である．マス $0 + 2 \times 1 = 2$ は存在し，$S_2 =$
oよりそこに石はないのでマス $2$ に移動する． - 現在位置はマス $2$ である．マス $2 + 3 \times 1 = 5$ は存在し，$S_5 =$
oよりそこに石はないのでマス $5$ に移動する． - 現在位置はマス $5$ である．マス $5 + 5 \times 1 = 10$ は存在し，$S_{10} =$
oよりそこに石はないのでマス $10$ に移動する．
としてマス $10$ に移動でき，次の操作で $k = 1$ と選ぶと
- 現在位置はマス $10$ である．マス $10 + 2 \times 1 = 12$ は存在し，$S_{12} =$
oよりそこに石はないのでマス $12$ に移動する． - 現在位置はマス $12$ である．マス $12 + 3 \times 1 = 15$ は存在し，$S_{15} =$
oよりそこに石はないのでマス $15$ に移動する． - 現在位置はマス $15$ である．マス $15 + 5 \times 1 = 20$ は存在し，$S_{20} =$
oよりそこに石はないのでマス $20$ に移動する．
としてマス $N = 20$ に移動できます．
一方最初の操作で $k = 2$ と選ぶと
- 現在位置はマス $0$ である．マス $0 + 2 \times 2 = 4$ は存在するが，$S_4 =$
xよりそこに石があるので転倒する．
となり転倒してしまいます．
また最初の操作で $k = 10$ と選ぶと
- 現在位置はマス $0$ である．マス $0 + 2 \times 10 = 20$ は存在し，$S_{20} =$
oよりそこに石はないのでマス $20$ に移動する． - 現在位置はマス $20$ である．マス $20 + 3 \times 10 = 50$ は存在しないので転倒する．
となり転倒してしまいます（操作は中断できません）．
転倒しない移動方法は冒頭で述べた $1$ 通りのみなので，$1$ を $998244353$ で割った余りである $1$ を出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。