103045: [Atcoder]ABC304 F - Shift Table
Description
Score : $525$ points
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
Input
题意翻译
给出长度为 $2\le n\le 10^5$ 仅由 `#` 和 `.` 的字符串 $s$，对于任意的 $m|n(0<m<n)$，你可以决定字符串 $t$ 的前 $m$ 个位置是 `#` 还是 `.`，对于第 $i>m$ 个位置，字符与第 $i-m$ 个位置相同。要求对于位置 $1\le i\le n$ 字符串 $s$ 和 $t$ 必须有一个是 `#`。注意不同的 $m$ 可能有相同的方案。问 $t$ 的方案数对 $998244353$ 取模的结果。Output
问题描述
Takahashi 和 Aoki 将在未来 $N$ 天做兼职工作。
Takahashi 的排班表是一个字符串 $S$，其中 $S$ 的第 $i$ 个字符为 # 表示他将在第 $i$ 天工作，而 . 表示他将在第 $i$ 天休息。
根据这个，Aoki 创建了他的排班表如下。
- 首先，选择一个正除数 $M$，且 $M$ 不等于 $N$。
- 其次，决定前 $M$ 天的出勤情况。
- 最后，按照顺序为 $i = 1, 2, \ldots, N - M$，决定第 $(M + i)$ 天的出勤情况，使其与第 $i$ 天的出勤情况相匹配。
注意，不同的 $M$ 值可能导致最终排班表相同。
求满足在 $N$ 天中至少有一天 Takahashi 和 Aoki 其中一人工作的排班表的数量，对 $998244353$ 取模。
约束条件
- $N$ 是一个介于 $2$ 和 $10^5$ 之间的整数，包括 $2$ 和 $10^5$。
- $S$ 是一个长度为 $N$ 的字符串，由
#和.组成。
输入
输入数据从标准输入中给出，格式如下：
$N$ $S$
输出
输出答案。
样例输入 1
6 ##.#.#
样例输出 1
3
Takahashi 在第 $1$、$2$、$4$ 和 $6$ 天工作。
假设 $T$ 表示 Aoki 的排班表，其中 $T$ 的第 $i$ 个字符为 # 表示他将在第 $i$ 天工作，而 . 表示他将在第 $i$ 天休息。
对于 $T$，有三个可能的字符串：######、#.#.#. 和 .##.##。
第一个排班表可以通过选择 $M = 1$ 或 $2$ 或 $3$ 实现，第二个排班表可以通过选择 $M = 2$ 实现，第三个排班表可以通过选择 $M = 3$ 实现。
样例输入 2
7 ...####
样例输出 2
1
样例输入 3
12 ####.####.##
样例输出 3
19