[Str记录]Uoj#429. 【集训队作业2018】串串划分
command_block
·
·
个人记录
题意 ： 给你一个长度为 n 的字符串 S ，你需要将其划分成若干个不相交的非空连续子串 s_1,s_2, ... , s_k(k \ge 1)，满足：
$n\leq 2\times 10^5$ ，时限$\texttt{1s}$。
------------
配合 [Blog : Lyndon & Runs](https://www.luogu.com.cn/blog/command-block/lyndon-runs) 食用。
这是 WC2019《The Runs Theorem and Lyndon Tree》 课件中的例题。
对于任意一个划分 $D=s_1s_2...s_m$ ，定义其贡献系数为 $F(D)=f(s_1)f(s_2)...f(s_m)$。
要求对于一个合法的划分 $D$ ，必有 $F(D)=1$ ，其余的非法划分的 $F$ 的和为 $0$。
若只需要满足第一个条件，直接令 $f(s)=[s\text{不是整循环串}]$ 即可。
但是还有条件二，这个条件和相邻两个串有关，不能针对每个划分单独设计，必须采用容斥。
设 $C(S)$ 为串 $S$ 的最小整循环节重复的次数，令 $f(s)=(-1)^{C(s)+1}$。
注意到若 $s=t$ ，则 $C(st)=C(s)+C(t)$ ，也即 $f(st)=-f(s)f(t)$。
若某个划分中有 $s_is_{i+1}$ 满足 $s_i=s_{i+1}$ ，则恰存在另一种划分将 $s_is_{i+1}$ 合在了一起（按照第一个不合法位置构成双射）。不难发现两者的贡献系数恰为相反数，所以，所有不合法的划分的贡献都抵消了。
设 $f[m]$ 为 $s[1,m]$ 的划分的贡献和，则有转移 ：
$$f[m]=\sum\limits_{i=1}^{m}(-1)^{C(S[i,m])+1}f[i-1]$$
若暴力转移，复杂度至少是 $O(n^2)$ 的，无法通过。
对于 $C(S[i,m])=1$ 的串，即非整循环串，可以前缀和搞定，只需特殊计算整循环串的贡献。
枚举在 $m$ 结尾的整循环串。
找出一个满足 $m\in[l,r]$ 的 ${\rm run}\ {\bf r}=(l,r,p)$ ，则在 $m$ 结尾的整循环串为 $[m-kp+1,m]\subseteq [l,r],k\in {\rm N},k\geq 2$。
不难发现这些串的起始位置是一个等差序列，随着 $m$ 的右移，等差序列会变长，在 $\bf r$ 内逐次补项即可做到 $O(1)$ 转移。
计算一下总复杂度 : 对于某个 ${\rm run}\ {\bf r}=(l,r,p)$ ，会对 $r-l+2-2p$ 个位置产生转移，求和后与我们求解本原平方串的复杂度相同，所以也为 $O(n\log n)$。
找 $m\in[l,r]$ 的 ${\rm run}$ 方便，不妨以 $O(n\log n)$ 的空间为代价事先将每个 $\rm run$ 发放到会导出转移的位置。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 200500
using namespace std;
const int mod=998244353;
template<const int mod,const int buf>
struct Hash
{
int p[MaxN],h[MaxN];
void InitH(char *s,int n){
p[0]=1;
for (int i=1;i<=n;i++){
p[i]=1ll*p[i-1]*buf%mod;
h[i]=(1ll*h[i-1]*buf+s[i]+1)%mod;
}
}
bool tl(int l,int r,int len)
{return ((h[l]-1ll*h[l-len]*p[len])-(h[r]-1ll*h[r-len]*p[len]))%mod==0;}
bool tr(int l,int r,int len)
{return ((h[l+len-1]-1ll*h[l-1]*p[len])-(h[r+len-1]-1ll*h[r-1]*p[len]))%mod==0;}
int get(int l,int r)
{return (h[r]+1ll*(mod-h[l-1])*p[r-l+1])%mod;}
};
Hash<926482651,29> h1;
Hash<1000000097,31> h2;
bool tl(int l,int r,int len)
{return h1.tl(l,r,len)&&h2.tl(l,r,len);}
bool tr(int l,int r,int len)
{return h1.tr(l,r,len)&&h2.tr(l,r,len);}
int n;char s[MaxN];
int extl(int u,int v)
{
int l=0,r=min(u,v),mid;
while(l<r){
mid=(l+r+1)>>1;
if (tl(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
int extr(int u,int v)
{
int l=0,r=n-max(u,v)+1,mid;
while(l<r){
mid=(l+r+1)>>1;
if (tr(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
struct Runs{int l,r,p;}b[MaxN<<1];
bool cmpR(const Runs &A, const Runs &B)
{return A.l==B.l ? (A.r==B.r ? A.p<B.p : A.r<B.r) : A.l<B.l;}
int tot;
void chk(int u,int v)
{
int tl=extl(u,v),tr=extr(u,v);
if (tl+tr>=v-u+1)
b[++tot]=(Runs){u-tl+1,v+tr-1,v-u};
}
bool cmpS(int u,int v){
int l=extr(u,v);
return s[u+l]<s[v+l];
}
int ly[MaxN],stk[MaxN],top;
void lyndon(bool op)
{
ly[n]=n;stk[0]=n+1;stk[top=1]=n;
for (int i=n-1;i;i--){
while(top&&cmpS(i,stk[top])==op)top--;
stk[++top]=i;
ly[i]=stk[top-1]-1;
}
}
void getRuns()
{
for (int op=0;op<=1;op++){
lyndon(op);
for (int i=1;i<n;i++)
chk(i,ly[i]+1);
}sort(b+1,b+tot+1,cmpR);
int m=0;
for (int i=1;i<=tot;i++)
if (b[i].l!=b[i-1].l||b[i].r!=b[i-1].r)
b[++m]=b[i];
tot=m;
}
vector<int> g1[MaxN],g2[MaxN];
ll f[MaxN],sf[MaxN],*rf[MaxN],_buf[MaxN<<5],*tb=_buf;
int main()
{
scanf("%s",s+1);n=strlen(s+1);
h1.InitH(s,n);h2.InitH(s,n);
getRuns();
for (int t=1;t<=tot;t++){
int l=b[t].l,r=b[t].r,p=b[t].p;
for (int i=l+2*p-1;i<=r;i++)g1[i].pb(t);
for (int i=l-1;i+2*p<=r;i++)g2[i].pb(t);
rf[t]=tb-l+1;tb+=r-l+2-p*2;
}
f[0]=sf[0]=1;
for (int t=0;t<g2[0].size();t++)
rf[g2[0][t]][0]=1;
for (int m=1;m<=n;m++){
f[m]=sf[m-1];
for (int t=0;t<g1[m].size();t++){
int tp=g1[m][t];
f[m]=(f[m]-2*rf[tp][m-2*b[tp].p])%mod;
}
for (int t=0;t<g2[m].size();t++){
int tp=g2[m][t];
rf[tp][m]=(f[m]+((b[tp].l<=m-2*b[tp].p+1) ? rf[tp][m-2*b[tp].p] : 0))%mod;
}
sf[m]=(sf[m-1]+f[m])%mod;
}printf("%lld",(f[n]+mod)%mod);
return 0;
}
```