题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=6987
题目大意：01串(S)可分割为(kp+p')，其中(p')是(p)的部分前缀，定义最大循环次数(k)为(v(s))，计算长度为(n)的01串(S)的(v(S))的和
题目思路：
定义(f(x))为长度为(n)，(v(S))为(x)的01串个数
则答案
[ans=sum_{x=1}^{n}left lfloor frac{n}{x}
ight
floor f(x)
]
长度为(x)的01串(T)共有(2^x)种情况，其中存在周期(y(y<x,ymid x))的情况显然不能被计算到(f(x))中，所以我们猜测
[f(x) = 2^x-sum_{ymid x,y<x}^{}f(y)
]
证明：
根据周期引理：若(x,y)是字符串(S)的周期且(x+y-gcd(x,y)leq |S|)，则(gcd(x,y))也是(S)的一个周期，此处的(x+y-gcd(x,y)leq |S|)等价于(xleqfrac{n}{2})
当(xleqfrac{n}{2})时，假设(T)不存在周期(y(y<x,ymid x))，而(S)有一个更小的周期(y)，根据周期引理，(gcd(x,y))也是(S)的一个周期，同时(gcd(x,y)mid x)，因此(gcd(x,y))也是(T)的一个周期，与我们假设的(T)相悖，因此(x)才是(S)的最小周期，可以用(f(x) = 2^x-sum_{ymid x,y<x}^{}f(y))计算
当(x > frac{n}{2})时，(f(x))的系数都是1，用总串数(2^n-[xleqfrac{n}{2}])的串数即可，公式可化为
[ans
=sum_{x=1}^{frac{n}{2}}left lfloor frac{n}{x}
ight
floor f(x) + 2^n - sum_{x=1}^{frac{n}{2}} f(x)\
=2^n+sum_{x=1}^{frac{n}{2}}(left lfloor frac{n}{x}
ight
floor-1)f(x)
]
可用分块计算，其中(f(x))前缀和可用杜教筛计算
[f(x) = 2^x-sum_{ymid x,y<x}^{}f(y)Rightarrow 2^x = sum_{ymid x}^{}f(y)=f*1
]
AC代码：
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 4e6 + 10, M = 31 * N;
const int max_n = 1e7 + 10;
const int base = 1e9;
const int P = 131;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
unordered_map<int, int> ans_f;
int f[N];
void init(int n)
{
int pow2 = 1;
for (int i = 1; i < n; ++i)
{
pow2 = (ll)pow2 * 2 % mod;
f[i] = pow2;
}
for (int i = 1; i < n; ++i)
for (int j = 2 * i; j < n; j += i)
f[j] = (f[j] - f[i] + mod) % mod;
for (int i = 1; i < n; ++i)
f[i] = (f[i] + f[i - 1]) % mod;
}
int ksm(int a, int b)
{
int res = 1 % mod;
while (b)
{
if (b & 1)
res = (ll)res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
int Sf(int n)
{
if (n < N)
return f[n];
if (ans_f.count(n))
return ans_f[n];
int res = ksm(2, n);
for (int l = 2, r; l <= n; l = r + 1)
{
r = min(n, n / (n / l));
res = (res - (ll)(r - l + 1) * Sf(n / l) % mod + mod) % mod;
}
return ans_f[n] = res;
}
int main()
{
init(N - 1);
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
int ans = ksm(2, n);
int pre = 0;
for (int l = 1, r; l <= n / 2; l = r + 1)
{
r = min(n, n / (n / l));
int now = Sf(r);
ans = (ans + (ll)(now - pre + mod) % mod * (n / l - 1) % mod) % mod;
pre = now;
}
printf("%d
", ans);
}
return 0;
}