AT_abc313_e [ABC313E] Duplicate

题目描述

给定一个只包含数字 $1$ 到 $9$ 的字符串 $S$，定义 $f(S)$ 为通过以下步骤得到的字符串 $T$（$S_i$ 表示 $S$ 的第 $i$ 个字符）：

• 有一个字符串 $T$。初始时，$T$ 是空字符串。
• 对于 $i=1,2,\dots,|S|-1$，依次进行如下操作：
  • 将 $S_{i+1}$ 作为整数，记为 $n$。在 $T$ 的末尾添加 $n$ 个 $S_i$。

例如，当 $S=313$ 时，$f(S)=3111$，操作过程如下：

• 初始时 $T$ 为空字符串。
• $i=1$ 时，$n=1$，在 $T$ 末尾添加 $1$ 个 3，$T$ 变为 3。
• $i=2$ 时，$n=3$，在 $T$ 末尾添加 $3$ 个 1，$T$ 变为 3111。
• 操作结束，得到 $T=3111$。

现在给定一个长度为 $N$ 的只包含 $1$ 到 $9$ 的字符串 $S$。你需要不断执行“将 $S$ 替换为 $f(S)$”的操作，直到 $S$ 的长度变为 $1$ 为止。

请输出在操作结束前所需操作的次数对 $998244353$ 取模的结果。如果操作会无限进行下去，请输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$

输出格式

输出操作结束前所需操作的次数对 $998244353$ 取模的结果。如果操作会无限进行下去，输出 $-1$。

输入输出样例 #1

输入 #1

3
313

输出 #1

4

输入输出样例 #2

输入 #2

9
123456789

输出 #2

-1

输入输出样例 #3

输入 #3

2
11

输出 #3

1

说明/提示

限制条件

• $2 \leq N \leq 10^6$
• $S$ 是由 $1$ 到 $9$ 组成的长度为 $N$ 的字符串

样例解释 1

当 $S=313$ 时，经过 $4$ 次操作后，$S$ 的长度变为 $1$。

• $f(S)=3111$，将 $S$ 替换为 3111。
• $f(S)=311$，将 $S$ 替换为 311。
• $f(S)=31$，将 $S$ 替换为 31。
• $f(S)=3$，将 $S$ 替换为 3。
• 此时 $S$ 的长度为 $1$，操作结束。

样例解释 2

当 $S=123456789$ 时，操作会无限进行下去。这种情况下应输出 $-1$。

由 ChatGPT 4.1 翻译