Score : $525$ points

问题描述

Takahashi 和 Aoki 将在接下来的 $N$ 天内兼职工作。
Takahashi 的轮班计划由字符串 $S$ 给出，其中 $S$ 的第 $i$ 个字符是 # 表示他在第 $i$ 天上班，. 表示他在第 $i$ 天缺席。
基于此，Aoki 按照以下方式创建了他的轮班计划：

• 首先，取一个不等于 $N$ 的正整数 $M$，要求它是 $N$ 的因子。
• 其次，决定前 $M$ 天的出勤情况。
• 最后，按照顺序对 $i = 1, 2, \ldots, N - M$，决定第 $(M + i)$ 天的出勤情况，使其与第 $i$ 天的出勤情况相同。

请注意，不同的 $M$ 值可能会导致相同的最终轮班计划。

找出满足条件的不同 Aoki 轮班计划的数量：在 $N$ 天中，Takahashi 和 Aoki 至少有一个每天都在工作，并将结果对 $998244353$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi and Aoki will work part-time for the next $N$ days.
Takahashi's shift schedule is given by the string $S$, where the $i$-th character of $S$ is # if he works on the $i$-th day, and . if he is absent on the $i$-th day.
Based on this, Aoki created his shift schedule as follows.

• First, take a positive divisor $M$ of $N$ that is not equal to $N$.
• Next, decide the attendance for the first $M$ days.
• Finally, for $i = 1, 2, \ldots, N - M$ in this order, decide the attendance for the $(M + i)$-th day so that it matches the attendance for the $i$-th day.

Note that different values of $M$ may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the $N$ days, modulo $998244353$.

Constraints

• $N$ is an integer between $2$ and $10^5$, inclusive.
• $S$ is a string of length $N$ consisting of # and ..

Input

The input is given from Standard Input in the following format:

$N$

$S$

Output

Print the answer.

Sample Input 1

6
##.#.#

Sample Output 1

3

Takahashi works on days $1$, $2$, $4$, and $6$.
Let $T$ be the string representing Aoki's shift schedule, where the $i$-th character of $T$ is # if he works on the $i$-th day, and . if he is absent on the $i$-th day.
There are three possible strings for $T$: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing $M = 1$ or $2$ or $3$, the second by choosing $M = 2$, and the third by choosing $M = 3$.

Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

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

Sample Output 3

19

update @ 2024/3/10 08:34:40