AT_abc304_f [ABC304F] Shift Table

题目描述

高桥君和青木君将在接下来的 $N$ 天里做兼职。
高桥君的排班表由字符串 $S$ 给出，$S$ 的第 $i$ 个字符为 # 时表示第 $i$ 天上班，为 . 时表示第 $i$ 天不上班。
基于此，青木君按照如下方式制作了自己的排班表：

• 首先，取 $N$ 的一个正因数 $M$，但 $M \neq N$。
• 接着，决定第 $1$ 天到第 $M$ 天的出勤情况。
• 最后，依次对 $i = 1, 2, \ldots, N - M$，令第 $M + i$ 天的出勤情况与第 $i$ 天相同。

需要注意的是，即使 $M$ 的取值不同，最终得到的排班表也可能相同。

请计算，在 $N$ 天中，每一天高桥君和青木君至少有一人上班的情况下，青木君的排班表可能有多少种，结果对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入读入。

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6
##.#.#

输出 #1

3

输入输出样例 #2

输入 #2

7
...####

输出 #2

1

输入输出样例 #3

输入 #3

12
####.####.##

输出 #3

19

说明/提示

限制条件

• $N$ 是 $2$ 到 $10^5$ 之间的整数。
• $S$ 是长度为 $N$ 的、仅由 # 和 . 组成的字符串。

样例解释 1

高桥君在第 $1, 2, 4, 6$ 天上班。用字符串 $T$ 表示青木君的排班表，$T$ 的第 $i$ 个字符为 # 时表示第 $i$ 天上班，为 . 时表示第 $i$ 天不上班。可能的 $T$ 有 ######、#.#.#.、.##.## 共 $3$ 种。第 $1$ 种排班表可以通过 $M = 1$ 或 $2$ 或 $3$ 实现，第 $2$ 种排班表可以通过 $M = 2$ 实现，第 $3$ 种排班表可以通过 $M = 3$ 实现。

由 ChatGPT 4.1 翻译