Cycle Binary – HDU 6987 – Virtual Judge (vjudge.net)

题意：对一个 01 串 $s$，设 $s$ 的权值是最大的 $k$，使得 $s$ 的某个前缀可以表示成一个相同的串重复 $k$ 次，并且剩余的部分一定是循环节的一个前缀。

现在给定 $n$，对所有长为 $n$ 的 01 串，求其权值的和。

关于循环节的问题肯定需要先知道长为 $n$ 的不循环的 01 串的个数。

实际上莫比乌斯反演一下就有

$$ f(n) = \sum_{d | n} \mu \left( \frac n d \right) 2 ^ d $$

考虑一个比较显然的性质，如果 $k \ge 2$，那么选择循环节的方法是唯一的。（又叫周期定理）

那么对于 $k$ 至少为 $2$ 的部分，贡献就是

$$ \begin{aligned}
& \sum_{d = 1} ^ {\left\lfloor \frac n 2 \right\rfloor} f(d) \left\lfloor\frac n d\right\rfloor \\
= & \sum_{d = 1} ^ {\left\lfloor \frac n 2 \right\rfloor} \left\lfloor\frac n d\right\rfloor \sum_{k | d} \mu \left( \frac d k \right) 2 ^ k \\
= & \sum_{k = 1} ^ {\left\lfloor \frac n 2 \right\rfloor} 2 ^ k \sum_{d = 1} ^ {\left\lfloor \frac n k \right\rfloor} \mu(d) \left\lfloor \frac n {dk} \right\rfloor
\end{aligned} $$

后面的和式显然分块求和再套一个 $\mu$ 的杜教筛就行了，那么外层也可以分块求和，写一个 $f$ 的前缀和即可。

另外关于 $k = 1$ 的部分，实际上它并不等于 $f(n)$ ，例如 abababa 就是反例。

正确的计算方法是用 $2^n$ 减去所有 $k\ge 2$ 的方案数，也就是 $2^n – \sum_{i = 1} ^ {\left\lfloor \frac n 2 \right\rfloor} f(i)$。这个东西之前一定计算过，直接拿来就好了。

为了优化复杂度，所有东西都预处理 $n ^ {\frac 2 3}$ 以内的部分。

本题主要的难点大概在于 $k = 1$ 时如何正确的统计方案数。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2000005, p = 998244353;
constexpr int table_size = 1000000;

int qpow(int a, int b) {
	int ans = 1;

	while (b) {
		if (b & 1)
			ans = (long long)ans * a % p;
		
		b >>= 1;
		a = (long long)a * a % p;
	}

	return ans;
}

int pwa[100005], pwb[100005];
constexpr int base = 100000;

int getpw(int n) {
	return (long long)pwa[n % base] * pwb[n / base] % p;
}

bool notp[maxn];
int prime[maxn / 10 + 5], prime_cnt;
int mu[maxn], f[maxn], mu_tbl[maxn], f_tbl[maxn];
int smu[maxn], sf[maxn];

int N;

void get_table() {
	const int n = table_size;

	mu[1] = 1;
	// f[1] = 2;

	for (int i = 2; i <= n; i++) {
		if (!notp[i]) {
			prime[++prime_cnt] = i;
			mu[i] = -1;
		}

		for (int j = 1; j <= prime_cnt && i * prime[j] <= n; j++) {
			notp[i * prime[j]] = true;

			if (i % prime[j])
				mu[i * prime[j]] = -mu[i];
			else
				break;
		}
	}

	for (int i = 1, pw = 1; i <= n; i++) {
		pw = pw * 2 % p;

		for (int j = i, k = 1; j <= n; j += i, k++) {
			f[j] += mu[k] * pw;

			if (f[j] < 0)
				f[j] += p;
			else if (f[j] >= p)
				f[j] -= p;
		}
	}

	for (int i = 1; i <= n; i++) {
		mu_tbl[i] = mu_tbl[i - 1] + mu[i];
		if (mu_tbl[i] < 0)
			mu_tbl[i] += p;
		else if (mu_tbl[i] >= p)
			mu_tbl[i] -= p;
		
		f_tbl[i] = (f_tbl[i - 1] + f[i]) % p;
	}
}

int getmu(int n) {
	if (n <= table_size)
		return mu_tbl[n];
	else if (smu[N / n])
		return smu[N / n];
	
	int ans = 0;

	for (int i = 2, last; i <= n; i = last + 1) {
		last = n / (n / i);
		ans = (ans + (long long)(last - i + 1) * getmu(n / i)) % p;
	}

	return smu[N / n] = (p + 1 - ans) % p;
}

int getsum(int l, int r) {
	return (getpw(r + 1) - getpw(l + 1) + p) % p;
}

int getf(int n) {
	if (n <= table_size) {
		// printf("Getf(%d) = %d\n", n, f_tbl[n]);
		return f_tbl[n];
	}
	else if (sf[N / n])
		return sf[N / n];
	
	int ans = 0;

	for (int i = 1, last; i <= n; i = last + 1) {
		last = n / (n / i);
		ans = (ans + (long long)getsum(i - 1, last) * getmu(n / i)) % p;
	}

	return sf[N / n] = ans;
}

int main() {
	pwa[0] = pwb[0] = 1;
	// int tpw = 1;

	for (int i = 1; i <= base; i++)
		pwa[i] = pwa[i - 1] * 2 % p;
	
	for (int i = 1; i < base; i++)
		pwb[i] = (long long)pwb[i - 1] * pwa[base] % p;
	
	get_table();

	ios::sync_with_stdio(false);

	/*
	for (int i = 1; i <= 10; i++)
		cout << "f[" << i << "] = " << f[i] << endl;
*/
	int T;
	cin >> T;

	while (T--) {
		cin >> N;

		int ans = (getpw(N) - getf(N / 2) + p) % p;

		// cerr << "ans = " << ans << "\n";

		for (int i = 1, last; i <= N / 2; i = last + 1) {
			last = N / (N / i);
			ans = (ans + (long long)(getf(last) - getf(i - 1) + p) * (N / i)) % p;
		}

		cout << ans << "\n";

		memset(sf, 0, sizeof(sf));
		memset(smu, 0, sizeof(smu));
	}

	return 0;
}