数字串 [分治+哈希+扩展KMP]

$Violence$Violence :

• 枚举子串, 复杂度 $O\left(N^2\right)$O(N2), 再 $O\left(N\right)$O(N)判断是否对答案做贡献.
  总复杂度 $O\left(N^3\right)$O(N3).

$Solution$Solution :

这道题目要求 快速地求出所有平方串的价值和,

首先整体使用分治处理.

假设现在整个串分为 $2$2 个串 $S_1,S_2$S1​, S2​ ;
$2$2 个串拼起来时会有新的 平方串 产生, 新的平方串分为 $2$2 种情况:

1. $mid$mid 在 $S_1$S1​ 上 .
2. $mid$mid 在 $S_2$S2​ 上 .
3. $mid$mid 在 $S_1$S1​, $S_2$S2​ 中间 .

以第二种情况为例分析 :

设当前 枚举的平方串长度 为 $2n$2n, 终点为 $i$i,
则 $i\in [n,2n-1]$i∈[n,2n−1] ,
则在 $S_1$S1​ 处的起点为 $t=\mid S_1\mid -(2n-i)+1$t=∣S1​∣−(2n−i)+1 .
$g=i-mid+1$g=i−mid+1

$.$                                                   .

对于该 平方串, $紫色$紫色 部分应相同, $棕色$棕色 部分应相同.

判断方法

$lcs$lcs 为最长公共后缀
$lcp$lcp 为最长公共前缀

$设$设
$le{n}_1=lcs\left\{S_1\right[1:\mid S_1\mid ],S_2[mid:g\left]\right\}le{n}_2=lcp\left\{S_2\right[1,mid],S_2[g,i\left]\right\}$len1​=lcs{S1​[1:∣S1​∣], S2​[mid:g]} len2​=lcp{S2​[1,mid],S2​[g,i]}
则只需要满足
$le{n}_1\>=\mid S_1\mid -(2n-i)+1le{n}_2\>=mid$len1​>=∣S1​∣−(2n−i)+1 len2​>=mid
即可满足 蓝色字体条件.

就说明该串是平方串.

判断部分可以使用 $Ex\_kmp$Ex_kmp $O(\mid S_1\mid +\mid S_2\mid )$ O(∣S1​∣+∣S2​∣) 完成.
配合 分治, 总的复杂度为 $O(n\ast logn)$O(n∗logn)

$Code$Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define SZ 1234567
const int MOD=666623333;
char*s,*t; int n,m,nx[SZ],ex[SZ];
void exkmp(bool g=0) {
	nx[1]=m; int a=0,p=0;
	for(int i=2;i<=m;++i) {
		int j=nx[i-a+1];
		if(i+j>p) for(j=max(0,p-i);i+j<=m&&t[i+j]==t[j+1];j++);
		nx[i]=j; if(i+j-1>p) a=i,p=i+j-1;
	}
	if(g) return;
	a=p=0;
	for(int i=1;i<=n;++i) {
		int j=nx[i-a+1];
		if(i+j>p) for(j=max(0,p-i+1);i+j<=n&&j<m&&s[i+j]==t[j+1];j++);
		ex[i]=j; if(i+j-1>p) a=i,p=i+j-1;
	}
}
char t1[SZ],t2[SZ];
int N,a[SZ],b[SZ]; char str[SZ];
ll h[SZ],q_[SZ],*q=q_+2,p10[SZ];
template<class T>
void ri(char*s1,int l1,char*s2,int l2,int g,int r,T op) {
	--s1; --s2;
	memcpy(t1,s1,sizeof(char)*(l1+1));
	memcpy(t2,s2,sizeof(char)*(l2+1));
	if(r) reverse(t1+1,t1+1+l1), reverse(t2+1,t2+1+l2);
	t=t2; m=l2; exkmp(1);
	for(int i=1;i<=l2;++i) b[i]=nx[i]; b[m+1]=0;
	reverse(t1+1,t1+1+l1); reverse(t2+1,t2+1+l2);
	s=t2; t=t1; n=l2; m=l1; exkmp();
	for(int i=1;i<=l2;++i) a[i]=ex[l2+1-i];
	for(int i=1;i<=l2;++i) {
		int L=i+i-a[i],R=b[i+1]+i;
		L=max(L,i+g); R=min(R,i+i-1); R=min(R,l2);
		if(L<=R) op(L,R,i);
	}
}
ll ans=0;
void op(int l,int r,int p) {
	ll hfs=q[r-p]-q[l-p-1];
	hfs-=p10[p]*(q[r-p-p]-q[l-p-p-1])%MOD;
	hfs=hfs%MOD*(p10[p]+1)%MOD; (ans+=hfs)%=MOD;
}
int padd=0;
inline void o1(int a,int b,int c){
        op(a+padd,b+padd,c);
}
inline void o2(int a,int b,int c){
        op(padd-b+c+c-1,padd-a+c+c-1,c);
}
void work(int l,int r) {
	if(l==r) return; 
	int m=(l+r)>>1;     
	work(l,m); work(m+1,r);
	padd=m; ri(str+l,m-l+1,str+m+1,r-m,0,0,o1);
	padd=m+1; ri(str+m+1,r-m,str+l,m-l+1,1,1,o2);
}
// {{{ KSM
ll qp(ll a,ll b) {
	ll x=1; a%=MOD;
	while(b) {
		if(b&1) x=x*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return x;
}
// }}}
int main(){
	FO(num) 
	p10[0]=1;
        for(int i=1;i<SZ;++i) p10[i]=p10[i-1]*10%MOD; // Get 10^i
	scanf("%s",str+1); N=strlen(str+1);
	for(int i=1;i<=N;++i) h[i]=(h[i-1]*10+str[i]-48)%MOD; // Hash
	for(int i=1;i<=N;++i)
		q[i]=(q[i-1]+((str[i+1]-'0')?h[i]:0))%MOD;    // Hash
	work(1,N); ll fm=N*(ll)(N+1)/2; fm%=MOD;
	ans=ans*qp(fm,MOD-2)%MOD; ans=(ans%MOD+MOD)%MOD;
	printf("%d\n",int(ans));
}