For a shift schedule \(X\), we define its period and minimum period as follows:

• \(X\) is said to have a period \(t\) if and only if the attendance of the \(i\)-th and \((i + t)\)-th days coincide for all \(1 \leq i \leq N-t\).
• \(X\) is said to have the minimum period \(t\) if and only if \(X\) has a period \(t\) but does not have a period \(s < t\).

Let \(A_t\) be the number of Aoki’s shift schedules with period \(t\) such that at least one of Takahashi and Aoki works, and \(M_t\) be the number of Aoki’s shift schedules with minimum period \(t\) such that at least one of Takahashi and Aoki works.

We want \(\displaystyle \sum_{t|N, t \neq N} M_t\). For every shift schedule of period \(t\), there is a unique divisor \(s\) of \(t\) such that the schedule has the minimum period \(s\), so \(A_t = \displaystyle \sum_{s|t} M_s\).

Since the period is simpler than the minimum period, making it easier to find \(A_t\) than \(M_t\), so we consider first finding \(A_t\), and then the answer using the equation \(A_t = \displaystyle \sum_{s|t} M_s\).

A shift schedule of period \(t\) is uniquely determined if the attendances of the \(1\)-st, \(2\)-nd, \(\ldots\), and \(t\)-th days are determined. Aoki can always attend on the \(i\)-th day; he can be absent on that day if and only if Takahashi attends on the \(j\)-th day if \(i \equiv j \pmod t\). Thus, \(A_t = 2^p\), where \(p\) is the number of \(i \in [1,t]\) such that Aoki can be absent on the \(i\)-th day.

This way, \(A_t\) are found; by the equation above, \(M_t\) are also found, so the answer is obtained.

\(A_t\) and \(M_t\) can be found in an \(O(N)\) time for each \(t\). Since it is sufficient to find them only for \(t\) that divides \(N\), so the overall time complexity is \(O(Nd(N))\), where \(d(N)\) is the number of divisors of \(N\). Under the constraints of this problem, \(N\) has at most \(120\) divisors, so this is fast enough.

Sample code

#include <iostream>
#include <vector>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = static_modint<998244353>;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<mint> p2(n + 1);
	p2[0] = 1;
	for (int i = 0; i < n; i++) p2[i + 1] = p2[i] * 2;
	vector<mint> a(n), m(n);
	for (int t = 1; t < n; t++) {
		if (n % t == 0) {
			vector<bool> v(t, true);
			for (int i = 0; i < n; i++) if (s[i] == '.') v[i % t] = false;
			int cnt = 0;
			for (int i = 0; i < t; i++) if (v[i]) cnt++;
			a[t] = p2[cnt];
			m[t] = a[t];
			for (int i = 1; i < t; i++) if (t % i == 0) m[t] -= m[i];
		}
	}
	mint ans = 0;
	for (int i = 1; i < n; i++) ans += m[i];
	cout << ans.val() << '\n';
}

Appendix 1: on the number of divisors of N

An integer \(N\) is said to be a highly composite number if and only if \(d(M) < d(N)\) if \(M < N\). The list of such numbers can be found in, for example, OEIS. Since the number of divisors of an integer not exceeding \(N\) is bounded by the number of divisors of the maximum highly composite number not exceeding \(N\), which yields the specific evaluation. Under the constraints of this problem, it is also easy to find the specific value of \(d(N)\).

Appendix 2: solution not using minimum period

Although it is not essentially different from the solution above, we can also use the Möbius function to represent the answer by \(\displaystyle \sum_{t|N, t \neq N} -\mu(\frac{N}{t}) A_t\). This way, you do not need to explicitly evaluate \(M_t\).