正題

題目鏈接:https://www.luogu.com.cn/problem/CF932G

---

題目大意

給出一個長度為$n$的字符串，將其分為$k$段（$k$為任意偶數(shù)），記為$p$。要求滿足對于任意$i$都有$p_i=p_{k?i+1}$。求方案數(shù)。

$1\le n\le 10^6$

---

解題思路

考慮將字符串化為$S_1{S}_n{S}_2{S}_{n?1}{S}_3{S}_{n?2}...$這樣的形式，可以發(fā)現(xiàn)對于原本相同的段在這里就被表示為了一個偶回文子串。

那么問題就變?yōu)榱藙澐秩舾蓚€偶回文子串。設(shè)$f_i$表示前$i$個的方案的話有一種比較簡單的做法，建立$PAM$后求出每個前綴的所有偶回文后綴，然后暴力轉(zhuǎn)移。

但是這樣的是$O(n^2)$的，時間復(fù)雜度不符合要求，考慮優(yōu)化。對于一個回文串來說它的所有回文后綴就是它的$border$。而$broder$有一個性質(zhì)就是所有$broder$的長度可以被劃分成$log$個等差數(shù)列。

我們可以在$PAM$上維護這些等差數(shù)列，記錄$to{p}_i$表示節(jié)點$i$所在的等差數(shù)列的頂部，然后每次使用$top$往上跳。加入新的$x$節(jié)點（或者覆蓋以前的已經(jīng)有的節(jié)點）的時候累計一下自己作為末尾時所在等差數(shù)列方案和就好了

時間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10,P=1e9+7; int n,cnt,pos[N],len[N],dis[N],fa[N],top[N],ch[N][26]; char t[N],s[N];int f[N],g[N]; int jump(int x,int p){while(s[p-len[x]-1]!=s[p])x=fa[x];return x; } int Insert(int x,int p){x=jump(x,p);int c=s[p]-'a';if(!ch[x][c]){++cnt;len[cnt]=len[x]+2; int y=jump(fa[x],p);fa[cnt]=ch[y][c];y=cnt;dis[y]=len[y]-len[fa[y]];if(dis[y]!=dis[fa[y]])top[y]=y;else top[y]=top[fa[y]];ch[x][c]=y;}return ch[x][c]; } int main() {scanf("%s",t+1);n=strlen(t+1);if(n&1)return puts("0")&0;for(int i=1;i<=n;i+=2)s[i]=t[i/2+1];for(int i=2;i<=n;i+=2)s[i]=t[n-i/2+1];len[1]=-1;fa[0]=top[1]=cnt=1;for(int i=1;i<=n;i++)pos[i]=Insert(pos[i-1],i);f[0]=1;for(int i=1;i<=n;i++){for(int x=pos[i];x;x=fa[top[x]]){g[x]=f[i-len[top[x]]];if(x!=top[x])(g[x]+=g[fa[x]])%=P;if(!(i&1))(f[i]+=g[x])%=P;}}printf("%d\n",f[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF932G-Palindrome Partition【PAM】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。