P11284 Solution

· · 题解

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;