シフト表 \(X\) に対し、周期および最小周期を以下のように定義します。

• 任意の \(1 \leq i \leq N-t\) に対し \(i\) 日目と \(i + t\) 日目の勤怠が一致しているとき、またそのときに限り\(X\) が周期 \(t\) を持つという。
• \(X\) が周期 \(t\) を持ち、\(s < t\) ならば \(X\) が周期 \(s\) を持たないとき、\(X\) は最小周期 \(t\) を持つという。

\(A_t\) を高橋君と青木君の少なくとも一方が出勤するという条件が満たされるような青木君の周期 \(t\) のシフトとして考えられるものの個数、\(M_t\) を高橋君と青木君の少なくとも一方が出勤するという条件が満たされるような青木君の最小周期 \(t\) のシフトとして考えられるものの個数とします。

求めるものは \(\displaystyle \sum_{t|N, t \neq N} M_t\) です。また、周期 \(t\) のすべてのシフト表に対し \(t\) の約数 \(s\) が一意に存在して最小周期 \(s\) を持つので、\(A_t = \displaystyle \sum_{s|t} M_s\) が成立します。

周期は最小周期に比べ構造が単純であり \(A_t\) は \(M_t\) より求めやすいので、先に \(A_t\) たちを求め、\(A_t = \displaystyle \sum_{s|t} M_s\) という関係式を利用して答えを求めることを考えます。

周期 \(t\) のシフト表は \(1, 2, \ldots, t\) 日目の勤怠を決めると一意に定まります。青木君が \(i\) 日目に出勤することは常に可能で、\(i\) 日目に欠勤できる必要十分条件は \(i \equiv j \pmod t\) ならば \(j\) 日目に高橋君が出勤することです。したがって、青木君が \(i\) 日目に欠勤できるような \(i \in [1,t]\) の個数を \(p\) として、\(A_t = 2^p\) です。

以上で \(A_t\) たちが求まり、上の関係式にしたがって \(M_t\) たちを求めることにより答えを得ることができました。

\(A_t\) や \(M_t\) たちは各 \(t\) に対して \(O(N)\) で求められ、\(t\) が \(N\) の約数であるときに限って求めればよいので時間計算量は \(N\) の約数の個数を \(d(N)\) として \(O(Nd(N))\) となります。本問題の制約下において \(N\) の約数は \(128\) 個以下であり、これは十分高速です。

実装例

#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';
}

補足 1 : N の約数の個数について

\(M < N\) ならば \(d(M) < d(N)\) というような条件を満たす整数 \(N\) は高度合成数 と呼ばれ、その値は OEIS などで確認できます。\(N\) 以下の整数の約数の個数は \(N\) 以下の最大の高度合成数の約数の個数で抑えられるので、これにより具体的な評価を得ることができます。また、本問題の制約下ではプログラムを書いて \(d(N)\) の具体的な値を評価することも簡単です。

補足 2 : 最小周期を経由しない解法

本質的には上の解法と大差ありませんが、メビウス関数を利用すれば答えは \(\displaystyle \sum_{t|N, t \neq N} -\mu(\frac{N}{t}) A_t\) と表せます。この解法においては陽に \(M_t\) を求める必要がありません。