Duplicate

题目描述

对于由数字 $1$ 到 $9$ 组成的字符串 $S$，令 $f(S)$ 为按照下述过程得到的字符串 $T$.（$S_i$ 表示 $S$ 的第 $i$ 个字符。）

令 $T$ 为初始为空的字符串。 对于 $i=1,2,\dots,|S|-1$，执行以下操作： 将 $n$ 个 $S_i$ 的副本追加到 $T$ 的末尾，其中 $n$ 是将 $S_{i+1}$ 作为整数解释时的值。

例如，$S=$ $313$ 通过以下步骤得到 $f(S)=$ $3111$。

$T$ 初始为空。 对于 $i=1$，我们有 $n=1$。将一个 $3$ 的副本追加到 $T$，此时 $T$ 变为 $3$。 对于 $i=2$，我们有 $n=3$。将三个 $1$ 的副本追加到 $T$，此时 $T$ 变为 $3111$。 终止该过程。我们得到 $T=$ $3111$。

给定一个长度为 $N$ 的字符串 $S$，由数字 $1$ 到 $9$ 组成。
你重复以下操作直到 $S$ 的长度变为 $1$：用 $f(S)$ 替换 $S$.
求你在完成该过程前执行该操作的次数，对 $998244353$ 取模。如果你将无限重复该操作，则输出 $-1$。

输入格式

输入从标准输入按以下格式给出： $N$ $S$

输出格式

输出在完成该过程前你执行该操作的次数对 $998244353$ 取模。如果你将无限重复该操作，则输出 $-1$。

3
313

4

9
123456789

-1

2
11

1

提示

$2 \leq N \leq 10^6$ $S$ 是一个长度为 $N$ 的由 $1,2,3,4,5,6,7,8,9$ 组成的字符串。如果 $S=$ $313$，则在四次操作后 $S$ 的长度变为 $1$。

我们有 $f(S)=$ $3111$。用 $3111$ 替换 $S$。 我们有 $f(S)=$ $311$。用 $311$ 替换 $S$。 我们有 $f(S)=$ $31$。用 $31$ 替换 $S$。 我们有 $f(S)=$ $3$。用 $3$ 替换 $S$。 现在 $S$ 的长度为 $1$，终止重复。
如果 $S=$ $123456789$，你将无限重复该操作。在这种情况下，应输出 $-1$.

标签: AtCoder|abc313E

来源

AtCoder|abc313E