https://vjudge.net/problem/QOJ-8543
给定 \(n\)，对于 \(i=1,2,\ldots,n\) 求出最长可能的周期字符串序列长度 F(i)，满足序列中字符串的长度 \(≤i\)。一个字符串序列 \(S_1,S_2,\ldots,S_l\) 是周期字符串序列，当且仅
当对于每个 \(1≤i<l\) 都满足 \(S_i\) 是 \(S_{i+1}\) 的周期，并且它们两两不同。（n<=2e5）
先求单个 F(n)。
手玩几下，发现：第一个串一定是长为 n 的，并且一定是 abbbb... 形式。
:abbbb
:abbb
abbba
:abb
abbab
abba
abbaa
:ab
ababa
abab
aba
abaab
abaa
abaaa
:a
aa
aaa
aaaa
aaaaa
观察冒号处的前缀最小值。后面拖了一段串。抓 ab 领导的这一段分析：
- 抓出
ab后的每一个a开头的串，形似整数拆分； - 整数拆分是有序的；
- 拆分的整数都不能超过开头
ab串的长度（2）。 - 被拆分的整数不超过 n-|
ab|。
即求序列 x 的个数，使得 \(\sum x\le n\)，\(x_i\le x_1\)。
枚举开头 abb... 串的长度 x1=k，得 F(n) 的生成函数：
\[\frac1{1-x}\sum_{k\ge1}\frac{x^k}{1-\sum_{1\le i\le k}x^i}=\frac1{1-x}\sum_{k\ge1}\frac{x^k}{1-\frac{x-x^{k+1}}{1-x}} \]外面乘的 \(\frac1{1-x}\) 是因为总和不超过 n 而不是恰好等于 n。
化简：
\[\sum_{k\ge1}\frac{x^k}{1-(2x-x^{k+1})} \]\(k\le\sqrt n\) 时，暴力计算贡献。具体来说，不断地给初始多项式 \(x^k\) 乘上 \((2x-x^{k+1})\)，再加上 \(x^k\)。可以写成完全背包转移。
\(k>\sqrt n\) 时，化原式：
\[\begin{aligned}&\frac{x^k}{(1-2x)(1-\frac{-x^{k+1}}{1-2x})}\\ =&\frac{x^k}{1-2x}\sum_{j\ge0}\left(\frac{-x^{k+1}}{1-2x}\right)^j\\ =&\sum_{j\ge0}(-1)^{j}\frac{x^{(k+1)j+k}}{(1-2x)^{j+1}} \end{aligned}\]显然 \(j\le\sqrt n\) 的是有用的。\(j\) 从大到小枚举，加完贡献后乘 \(\frac1{1-2x}\)，还是完全背包转移。
看 Dairuichen007 学会的代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
const int NV=3e3;
ll mod;
namespace xm{
int N,ans[NV+5],f[NV+5],g[NV+5];
void lB(int k){
memset(f,0,sizeof f);
f[k]=1;
for(int i=k+1;i<=N;++i) f[i]=(2ll*f[i-1]+mod-f[i-k-1])%mod;
for(int i=1;i<=N;++i) ans[i]=(ans[i]+f[i])%mod;
}void _(){
scanf("%d%lld",&N,&mod);
int B=sqrt(N);
for(int i=1;i<=B;++i) lB(i);
for(int x=B;~x;--x){
for(int k=B+1;k<=N;++k){
const int i=(k+1)*x+k;
if(i<=N) g[i]=(g[i]+(x&1?mod-1:1))%mod;
}
for(int i=1;i<=N;++i) g[i]=(g[i]+2ll*g[i-1])%mod;
}
for(int i=1;i<=N;++i) ans[i]=(ans[i]+g[i])%mod;
for(int i=1;i<=N;++i) printf("%lld ",ans[i]); puts("");
}
}
int main(){
xm::_();
return 0;
}