自动搬运

查看原文

来自洛谷，原作者为

	vzcx_host vzcx 系列第一站

搬运于2025-08-24 23:06:05，当前版本为作者最后更新于2024-11-18 17:26:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 24/11/22：回味子串没了，修订了一下表述错误。

记录赛时的爆标做法。

考虑设 $f_i$ 为长度为 $i$ 且不存在前缀回文子串的字符串数量，显然可以容斥，其暴力转移式为：

$$f_i=m^i-\sum_{j=1}^{\lfloor i/2\rfloor}f_j m^{i-2j} $$

令 $w=m^{-1},g_i=f_i\times w^{2i}$，有：

$$g_i=w^i(1-\sum_{j=1}^{\lfloor i/2\rfloor}g_j)$$

对于一个可以成为答案字符串，我们选择前缀回文子串中长度最短的串作为枚举对象，可以证明，若一个字符串存在前缀回文子串，其最短的前缀回文子串一定不长于原串的半长。枚举前缀回文子串的半长 $i$，答案式子为：

$$\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}\sum_{j=0}^{n-3i} f_im^{i+j} $$$$=\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}f_i m^i(\dfrac{m^{n+1-3i}-1}{m-1}) $$$$=\dfrac{m^{n+1}\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}f_iw^{2i}-\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}f_im^i}{m-1} $$$$=\dfrac{m^{n+1}\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}g_i-\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor}g_im^{3i}}{m-1} $$

令 $v=w^{d+1}$ 考虑计算：

$$A(d,k)=\sum_{i=1}^{k}g_iw^{di}$$ $$=\sum_{i=1}^{k}w^{di}(w^i(1-\sum_{j=1}^{\lfloor i/2\rfloor}g_j)) $$$$=\sum_{i=1}^{k}v^i-\sum_{i=1}^{k}\sum_{j=1}^{\lfloor i/2\rfloor}v^ig_j $$$$=\sum_{i=1}^{k}v^i-\sum_{j=1}^{\lfloor k/2\rfloor}g_j\sum_{i=2j}^{k}v^i $$$$=\dfrac{v^{k+1}-v}{v-1}-\dfrac{\sum_{j=1}^{\lfloor k/2\rfloor}g_j(v^{k+1}-v^{2j})}{v-1} $$$$=\dfrac{v^{k+1}-v}{v-1}-\dfrac{v^{k+1}A(0,\lfloor k/2\rfloor)-A(2d+2,\lfloor k/2\rfloor)}{v-1} $$

递归计算即可，容易证明状态总数是 $O(\log^2 n)$ 的，根据实现的精细程度可以做到 $O(\log^2 n)$ 或 $O(\log^3 n)$。赛时代码为后者。

upd：新增没有细节判断的 $O(\log^2 n)$ 代码，该代码在洛谷上单测试点最慢为 4ms：

val[0]=0;
for(int i=1;i<=64;i++)
    val[i]=(val[i-1]*2+2)%(mod-1);
vkc[ln=0]=n/3;
while(vkc[ln]!=1){vkc[ln+1]=vkc[ln]/2;ln++;}
for(int i=0;i<=ln;i++){
    vkg[i]=Pow(w,val[i]+1);
    nkg[i]=Pow(vkg[i]-1,mod-2);
    vd[ln][i]=dp[ln][i]=vkg[i];
}
for(int i=ln-1;i>=0;i--)
    for(int j=0;j<=i;j++){
        vd[i][j]=vd[i+1][j]*vd[i+1][j]%mod;
        if(vkc[i]&1)vd[i][j]=vd[i][j]*vkg[j]%mod;
        vx=vd[i][j]*vkg[j]%mod;
        dp[i][j]=(vx+mod-vkg[j]+mod-(vx*dp[i+1][0]+mod-dp[i+1][j+1])%mod)*nkg[j]%mod;
    }
ans=Pow(m,(n+1)%(mod-1))*dp[0][0]%mod;
now=mod-4;vg=1;
for(int i=0;i<ln;i++){
    v=Pow(w,now+1);vx=Pow(v,vkc[i]+1);vg=vg*Pow(v-1,mod-2)%mod;
    ans+=mod-vg*(vx+mod-v+mod-vx*dp[i+1][0]%mod)%mod;
    now=(now*2+2)%(mod-1);
}
ans+=mod-vg*Pow(w,now+1)%mod;