[C++知识库]?·M·e·r·c·u·r·y·? AC自动机·杂题选做

P8011 「Wdsr-3」蓬莱药局

多串匹配，考虑$AC$自动机。

因为$2^t$个串是独立的，所以算出一个的概率乘上$2^t$就好了。

设$dp[i][j]$表示前$i$个位置，走到$AC$自动机上$j$这个节点，模式串的出现次数是奇数的概率，设$f[i][j]$为总概率。

设$cnt[i]$为模数串在$i$节点代表的节点中出现次数的奇偶性，那么转移时枚举这一位是什么字符，乘上对应的概率。

并且因为要求是奇数，所以转移完要看看如果某个节点的$cnt$为1，也就是说走到这个节点就会让奇偶性改变，那么概率取反，也就是用总集$f[i][j]$减掉不合法的$g[i][j]$。

同时，因为转移可以写成矩阵乘法的形式，所以我们可以提前把概率的矩阵做一下K次幂，因为矩阵乘法具有结合律。

同时因为对前两个点这样的话跑不过，需要数据分治一下。

第一个点直接就AC自动机匹配就好了，第二个点瓶颈在于矩阵乘法，不过发现只会出现数字1，那么我们只需要把不是1的压成一块就好了。

#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int mod = 1e9+7;
inline int myplus(int a,int b){return (a+b)>=mod?a+b-mod:a+b;}
inline int reduce(int a,int b){return (a-b<0?a-b+mod:a-b);}
int n,m,k,t;
const int N = 1e6+7;
int tr[N][101];
int cnt[N],f[2][N],g[2][N];
int Next[N];
int A,a[N];
int S[N];
int tot=0;
void Extend()
{
	int p=0;
	for(int i=1;i<=A;i++)
	{
		int c=a[i];
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	}
	cnt[p]^=1;
}
queue<int> q;
int L=2;
void Build()
{
	for(int i=1;i<=L;i++)
	if(tr[0][i]) q.push(tr[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		cnt[x]^=cnt[Next[x]];
		for(int c=1;c<=L;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[y]=tr[Next[x]][c];
				q.push(y);
			} 
		}
	}
}
int P[1200][1200],Q[1200][1200],R[1200][1200];
void mulPP()
{
	for(int i=1;i<=k;i++)
	for(int j=1;j<=k;j++)
	R[i][j]=0;
	for(int i=1;i<=k;i++)
	for(int j=1;j<=L;j++)
	for(int l=1;l<=L;l++)
	R[i][j]=myplus(R[i][j],1ll*P[i][l]*P[l][j]%mod);
	for(int i=1;i<=k;i++)
	for(int j=1;j<=L;j++)
	P[i][j]=R[i][j];
}
void mulQP()
{
	for(int i=1;i<=k;i++)
	for(int j=1;j<=k;j++)
	R[i][j]=0;
	for(int i=1;i<=k;i++)
	for(int j=1;j<=L;j++)
	for(int l=1;l<=k;l++)
	R[i][j]=myplus(R[i][j],1ll*Q[i][l]*P[l][j]%mod);
	for(int i=1;i<=k;i++)
	for(int j=1;j<=k;j++)
	Q[i][j]=R[i][j];
}
void Powerful(int B)
{
	for(int i=1;i<=k;i++)
	Q[i][i]=1;
	while(B)
	{
		if(B&1) mulQP();
		mulPP();
		B>>=1;
	}
}
int Pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
int main()
{
	read(n);read(m);read(k);read(t);
	for(int i=1;i<=n;i++)
	read(S[i]);
	for(int i=1;i<=m;i++)
	{
		read(A);
		for(int j=1;j<=A;j++)
		read(a[j]);
		Extend();
	}
	for(int i=1;i<=k;i++)
	{
		int sum=0;
		for(int j=1;j<=k;j++)
		{
			read(P[i][j]);
			sum=myplus(sum,P[i][j]);
		}
		sum=Pow(sum,mod-2);
		for(int j=1;j<=k;j++)
		P[i][j]=1ll*P[i][j]*sum%mod;
	}
	if(k>100)
	{
		for(int i=1;i<=k;i++)
		{
			P[i][2]=reduce(1,P[i][1]);
			for(int j=3;j<=k;j++)
			P[i][j]=0;
		}
		L=2;
	}
	else L=k;
	Build();
	if(!t)
	{
		int ans=0;
		int p=0;
		for(int i=1;i<=n;i++)
		{
			int c=S[i];
			p=tr[p][c];
			ans^=cnt[p];
			printf("%d\n",ans);
		}
		return 0;
	}
	Powerful(t);
	f[0][0]=1;
	int K=Pow(2,t);
	int *f0=f[0],*f1=f[1],*g0=g[0],*g1=g[1];
	for(int i=1;i<=n;i++,swap(f0,f1),swap(g0,g1))
	{
		for(int x=0;x<=tot;x++)
		f1[x]=g1[x]=0;
		for(int x=0;x<=tot;x++)
		{
			if(!f0[x])continue;
			for(int c=1;c<=k;c++)
			{
				int y=tr[x][c];
				f1[y]=myplus(f1[y],1ll*f0[x]*Q[S[i]][c]%mod);
				g1[y]=myplus(g1[y],1ll*g0[x]*Q[S[i]][c]%mod);
			}
		}
		int ans=0;
		for(int x=0;x<=tot;x++)
		{
			if(cnt[x]) g1[x]=reduce(f1[x],g1[x]);
			ans=myplus(ans,g1[x]);
		}
		printf("%lld\n",1ll*ans*K%mod);
	}
	return 0;
}

[JRKSJ R4] Salieri

把文本串在AC自动机上跑，走到一个点就给这个点到根的路径权值加1，那么每个点的权值就是出现次数。

可以想到建出所有走过的点的虚树，那么一条虚路径的权值是相同的。

那么我们就是要求$cnt\times w$的$k$的值。

二分答案，对于每个链单独判断，因为$cnt$是相等的，所以就是求

$$w\ge ?\frac{ans}{cnt}?$$
的个数，用主席树维护就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
int tr[N][4];
int n,m;
char s[N];
int v[N];
int End[N];
int tot=1;
vector<int> adj[N];
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
int Next[N]; 
void Extend(int x)
{
	int p=1;
	int len=strlen(s+1);
	for(int i=1;i<=len;i++)
	{
		int c=s[i]-'a';
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	}
	End[x]=p;
	adj[p].push_back(x);
}
queue<int> q;
int rot[N];
const int M = 1e7+7;
int lson[M],rson[M],cnt[M];
int idx=0;
inline int clone(int x)
{
	int k=++idx;
	lson[k]=lson[x];
	rson[k]=rson[x];
	cnt[k]=cnt[x]+1;
	return k;
}
int ins(int A,int l,int r,int x)
{
	int k=clone(A);
	if(l==r)return k;
	int mid=(l+r)>>1;
	if(x<=mid) lson[k]=ins(lson[A],l,mid,x);
	else rson[k]=ins(rson[A],mid+1,r,x);
	return k;	
}
int ask(int x,int y,int l,int r,int L,int R)
{
	if(L>R)return 0;
	if(!y) return 0;
	if(L<=l&&r<=R) return cnt[y]-cnt[x];
	int mid=(l+r)>>1;
	int res=0;
	if(L<=mid) res+=ask(lson[x],lson[y],l,mid,L,R);
	if(R>mid) res+=ask(rson[x],rson[y],mid+1,r,L,R);
	return res;
}
int top[N],fa[N],dep[N],siz[N],son[N]; 
int dfn[N],timer=0;
void dfs(int x)
{
	dfn[x]=++timer;
	siz[x]=1;
	rot[x]=rot[fa[x]];
	for(auto u:adj[x])
	rot[x]=ins(rot[x],1,1000,v[u]);
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		fa[y]=x;
		dep[y]=dep[x]+1;
		dfs(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]])son[x]=y;
	}
}
void Exdfs(int x,int topth)
{
	top[x]=topth;
	if(!son[x])return ;
	Exdfs(son[x],topth);
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==fa[x]||y==son[x])continue;
		Exdfs(y,y);
	}
}
int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
void Build()
{
	for(int c=0;c<4;c++)
	tr[0][c]=1;
	q.push(1);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int c=0;c<4;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[y]=tr[Next[x]][c];
				q.push(y);
			}
		}
	}
	for(int i=2;i<=tot;i++)
	add(Next[i],i);
	dfs(1);
	Exdfs(1,1);
}
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
int h[N];
int sta[N],tp=0,K=0;
void Extract()
{
	sort(h+1,h+K+1,cmp);
	t=0;
	tp=0;
	sta[++tp]=1;
	link[1]=0;
	for(int i=1;i<=K;i++)
	{
		if(h[i]==1||h[i]==h[i-1]) continue;
		int lca=LCA(h[i],sta[tp]);
		if(lca!=sta[tp])
		{
			while(dfn[sta[tp-1]]>dfn[lca]) 
			add(sta[tp-1],sta[tp]),tp--;
			if(sta[tp-1]!=lca)
			{
				link[lca]=0;
				add(lca,sta[tp--]);
				sta[++tp]=lca;
			}
			else  add(lca,sta[tp--]);
		}
		link[h[i]]=0;
		sta[++tp]=h[i];
	}
	for(int i=1;i<tp;i++)
	add(sta[i],sta[i+1]);
}
int tim[N];
void getsiz(int x)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		getsiz(y);
		tim[x]+=tim[y];
	}
}
void getclr(int x)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		getclr(y);
	}
	tim[x]=0;
}
template <typename T>inline void read(T &x)
{
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
int Ans=0;
int ceil(int x,int y)
{
	if(x%y==0) return x/y;
	return x/y+1;
}
void getans(int x,int limit)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		getans(y,limit);
		Ans+=ask(rot[x],rot[y],1,1000,ceil(limit,tim[y]),1000);
//		cout<<x<<'-'<<y<<' '<<ceil(limit,tim[y])<<' '<<ask(rot[x],rot[y],1,1000,1,1000)<<endl;
	}
}
int account(int mid)
{
	Ans=0;
	getans(1,mid);
	return Ans;
}
int main()
{
	read(n);read(m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		read(v[i]);
		Extend(i);
	}
	Build();
	while(m--)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		int k;
		read(k);
		K=0;
		int p=1;
		for(int i=1;i<=len;i++)
		{
			int c=s[i]-'a';
			p=tr[p][c];
			h[++K]=p;
			tim[p]++;
		}
		Extract();
		getsiz(1);
		int l=1,r=1e9,mid,ans=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(account(mid)>=k)
			{
				ans=mid;
				l=mid+1;
			} 
			else r=mid-1;
		}
		getclr(1);
		printf("%d\n",ans);
	}
	return 0;
}

DDOSvoid 的馈赠

官方题解太神了，写了个较劣的做法。

首先建出AC自动机，设$F[x]$为$x$到根的路径上经过的字符串的集合，用$bitset$存一下。可以在建AC自动机的时候存出来。

设$G[x]$为$t_x$的子串集合，这个只需要把这个串在AC自动机上跑，然后求经过所有节点的$F$的并就行了。

询问可以直接合并两个bitset。

时间复杂度$O(\frac{n^2+nm+nq}{w})$可以冲过去，但是空间不太行。

考虑把$n$分块，每块分别处理，这样空间就变成了了$O(\frac{n+mB}{w})$

在空间保证的情况下B可以取大点。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int tr[N][26];
int Next[N];
int End[N];
char str[N];
int tot=0; 
const int B=18000;
char s[N];
bitset<B> F[N],H[N];
void Extend(int x,int l,int r)
{
	int p=0;
	for(int i=l;i<=r;i++)
	{
		int c=s[i]-'a';
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	}
	F[p][x]=1;
}
queue<int> q;
void Build()
{
	for(int c=0;c<26;c++)
	if(tr[0][c]) q.push(tr[0][c]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		F[x]|=F[Next[x]];
		for(int c=0;c<26;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[y]=tr[Next[x]][c];
				q.push(y);
			}
		}
	}
}
int n,m,Q;
int l[N],r[N];
char t[N];
int L[N],R[N];
int X[N],Y[N];
template <typename T>inline void read(T &x)
{
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
int lpos[N],rpos[N];
int bel[N],cnt;
int ans[N];
void clear()
{
	for(int i=0;i<=tot;i++)
	{
		F[i].reset();
		for(int c=0;c<26;c++)
		tr[i][c]=0;
		Next[i]=0;
	}
	tot=0;
	for(int i=1;i<=m;i++)
	H[i].reset();
}
int main()
{
	read(n);read(m);read(Q);
	int now=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		int len=strlen(str+1);
		l[i]=now+1;
		r[i]=l[i]+len-1;
		now=r[i];
		for(int p=1;p<=len;p++)
		s[l[i]+p-1]=str[p];
	}
	now=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		int len=strlen(str+1);
		L[i]=now+1;
		R[i]=L[i]+len-1;
		now=R[i];
		for(int p=1;p<=len;p++)
		t[L[i]+p-1]=str[p];
	}
	for(int i=1;i<=Q;i++)
	read(X[i]),read(Y[i]);
	for(int i=1;i<=n;i++)
	{
		bel[i]=(i-1)/B+1;
		rpos[bel[i]]=i;
		if(!lpos[bel[i]]) lpos[bel[i]]=i;
		cnt=bel[i];
	}
	for(int o=1;o<=cnt;o++)
	{
		clear();
		for(int i=lpos[o];i<=rpos[o];i++)
		Extend(i-lpos[o]+1,l[i],r[i]);
		Build();
		for(int i=1;i<=m;i++)
		{
			int p=0;
			for(int j=L[i];j<=R[i];j++)
			{
				int c=t[j]-'a';
				p=tr[p][c];
				H[i]|=F[p];
			} 
		}
		for(int i=1;i<=Q;i++)
		ans[i]+=(H[X[i]]&H[Y[i]]).count();
	}
	for(int i=1;i<=Q;i++)
	printf("%d\n",ans[i]);
	return 0;
} 

P6698 [BalticOI 2020 Day2] 病毒/CF1387C Viruses

考虑把匹配看成在$AC$自动机上走，那么就是强制不能匹配任何一个串，也就是说不能走到任何一个祖先链上有结束节点的点。

那么询问的就是最短路，答案为$Yes$可以看成无法到达，也就是最短路为正无穷。

设$f[c][x][y]$为把$c$字符变异后从$x$走到$y$的最短路。

考虑怎么求，我们用类似SPFA的方式转移，一开始把字符0和1放入队列里。

使用迭代来更新，每次用一个当前队首的字符c来更新其他的，那么只有当c存在于某个字符x的b序列里时，x才可能被更新，因此枚举出现过x的某个突变$o$。

考虑用这个突变来更新其他的$f$
。

枚举一个起点$S$,设$dp[i][x]$为考虑了突变序列的前i个位置，S到x号节点的最短路。

转移时简单的，$dp[i+1][y]=min(dp[i][x]+f[b[i][x][y]])$
所有的转移完了后看一下有没有某个值被更新了，如果被更新了，那么就把当前字符入队。

复杂度看起来很玄学，但是跑的还挺快的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 120;
int tr[N][2];
int n,m,K;
vector<int> appear[N];
int f[N][N][N],g[N][N];
bool adj[N];
int tot=0;
vector<int> b[N];
int a[N];
int k[N];
int s[N];
int l;
void Extend()
{
	int p=0;
	for(int i=1;i<=l;i++)
	{
		int c=s[i];
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	}
	adj[p]=1;
}
int Next[N];
queue<int> q;
void Build()
{
	for(int c=0;c<2;c++)
	if(tr[0][c]) q.push(tr[0][c]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		adj[x]|=adj[Next[x]];
		for(int c=0;c<2;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[y]=tr[Next[x]][c];
				q.push(y);
			}
		}
	}
}
template <typename T>inline void read(T &x)
{
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
int INF=1e18;
bool vis[N];
bool update(int o)
{
	bool rel=0;
	for(int S=0;S<=tot;S++)
	{
		memset(g,0x3f,sizeof(g));
		g[0][S]=0;
		for(int i=0;i<k[o];i++)
		{
			int c=b[o][i];
			for(int x=0;x<=tot;x++)
			{
				if(g[i][x]>=INF)continue;
				for(int y=0;y<=tot;y++)
				g[i+1][y]=min(g[i+1][y],g[i][x]+f[c][x][y]);
			}
		} 
		for(int x=0;x<=tot;x++)
		{
			if(g[k[o]][x]<f[a[o]][S][x])
			{
				f[a[o]][S][x]=g[k[o]][x];
				rel=1;
			}
		}	
	}
	return rel;
}
signed main()
{
	read(n);read(m);read(K);
	for(int i=1;i<=m;i++)
	{
		read(a[i]);read(k[i]);
		for(int j=0;j<k[i];j++)
		{
			int x;read(x);
			b[i].push_back(x);
			appear[x].push_back(i);
		}
	}
	for(int i=1;i<=K;i++)
	{
		read(l);
		for(int j=1;j<=l;j++)
		read(s[j]);
		Extend(); 
	}
	Build();
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	for(int i=0;i<=tot;i++)
	{
		if(adj[i])continue;
		for(int c=0;c<2;c++)
		{
			int y=tr[i][c];
			if(!adj[y]) f[c][i][y]=1;
		}
	}
	q.push(0);q.push(1);
	vis[0]=vis[1]=1;
	while(!q.empty())
	{
		int ch=q.front();
		q.pop();
		vis[ch]=0;
		for(auto i:appear[ch])
		{
			if(update(i)&&!vis[a[i]])
			{
				vis[a[i]]=1;
				q.push(a[i]);
			}
		}
	}
	for(int i=2;i<=n-1;i++)
	{
		int ans=INF;
		for(int x=0;x<=tot;x++)
		ans=min(ans,f[i][0][x]);
		if(ans>=INF) printf("YES\n");
		else printf("NO %lld\n",ans);
	}
	return 0;
}

CF585F Digits of Number Pi

显然是数位dp，先差分一下。

建出$AC$自动机，那么出现了长度大于$?\frac{d}{2}?$的子串，当且匹配时仅当经过了AC自动机上深度大于这个限制的点。

那么状态就很简单了。

设$dp[i][0/1][0/1][x]$表示填了前$i$个位置，是否卡上界，是否已经经过了符合的点，走到了AC自动机的某个点的方案数。

转移是简单的。

同样的因为我们只需要支持子串匹配，SAM也是可以的，就是能走就走，不能走就跳。

因为某些原因写的是SAM的版本。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+7;
const int mod = 1e9+7;
int n,m;
int len[N],tr[N][10],fa[N];
char s[N],A[N],B[N];
int tot=1,last=1;
void copy(int x,int y)
{
	fa[x]=fa[y];
	len[x]=len[y];
	for(int c=0;c<10;c++)
	tr[x][c]=tr[y][c];
} 
int hung[N][10];
void Extend(int c)
{
	int p=last,np=last=++tot;
	len[np]=len[p]+1;
	while(p&&!tr[p][c])
	{
		tr[p][c]=np;
		p=fa[p];	
	}	
	if(!p) fa[np]=1;
	else
	{
		int q=tr[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else
		{
			int nq=++tot;
			copy(nq,q);
			len[nq]=len[p]+1;
			fa[np]=fa[q]=nq;
			while(p&&tr[p][c]==q)
			{
				tr[p][c]=nq;
				p=fa[p];
			}
		}
	}
} 
int f[55][2020][55][2][2];
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
void dfs(int x)
{
	for(int c=0;c<10;c++)
	if(tr[x][c]) hung[x][c]=x;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		for(int c=0;c<10;c++)
		hung[y][c]=hung[x][c];
		dfs(y);
	}
}
int plu(int x,int y) 
{
	return (x+y>=mod?x+y-mod:x+y);
}
int mul(int x,int y)
{
	return 1ll*x*y%mod;
}
int a[N];
int dp(int x,int cur,int lenth,bool limit,bool ok)
{
	if(x==m+1) return ok;
	if(f[x][cur][lenth][limit][ok]!=-1) return f[x][cur][lenth][limit][ok];
	int up=(limit?a[x]:9);
	int res=0;
	for(int c=0;c<=up;c++) 
	{
		if(ok) res=plu(res,dp(x+1,cur,lenth,limit&&c==up,1));
		else
		{
			if(tr[cur][c]) res=plu(res,dp(x+1,tr[cur][c],lenth+1,limit&&c==up,(lenth+1)>=m/2));
			else
			{
				int p=hung[cur][c];
				if(p) res=plu(res,dp(x+1,tr[p][c],len[p]+1,limit&&c==up,(len[p]+1)>=m/2));
				else res=plu(res,dp(x+1,1,0,limit&&c==up,0));
			}			
		}
	}
	f[x][cur][lenth][limit][ok]=res;
	return res;
}
int main()
{
	scanf("%s %s %s",s+1,A+1,B+1);
	n=strlen(s+1);m=strlen(A+1);
	for(int i=1;i<=n;i++)
	Extend(s[i]-'0');
	for(int i=2;i<=tot;i++)
	add(fa[i],i);
	dfs(1);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=m;i++)
	a[i]=B[i]-'0';
	A[m]--;
	int o=m;
	while(A[o]=='0'-1)
	{
		A[o-1]--;
		A[o--]='9';
	} 
	int res=dp(1,1,0,1,0);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=m;i++)
	a[i]=A[i]-'0';
	res=(res-dp(1,1,0,1,0)+mod)%mod;
	cout<<res;
	return 0;
}

CF590E Birthday

前置知识：$Dilworth$定理。

可以看一下P4298 [CTSC2008]祭祀

匹配关系也是一种偏序关系。

建出AC自动机，然后把有子串关系的节点连边，那么就会有一个DAG，我们要找出最长反链。

建边可以用路径压缩，详情看代码。

剩下的就是上边的那个题里。

输出方案真恶心。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+7;
char s[N];
int S[N];
int tr[N][2],Next[N];
const int M = 755;
int End[N];
int St[M],Ed[M],len[M];
int tot=0;
int n,m;
void Insert(int x)
{
	scanf("%s",s+1);
	len[x]=strlen(s+1);
	St[x]=Ed[x-1]+1;
	Ed[x]=St[x]+len[x]-1;
	int p=0;
	for(int i=1;i<=len[x];i++)
	{
		int c=s[i]-'a';
		if(!tr[p][c]) tr[p][c]=++tot;
		S[++m]=c;
		p=tr[p][c];
	}
	End[p]=x;
} 
int pre[N];
bool vis[N];
queue<int> q;
void GetNxt()
{
	for(int c=0;c<2;c++)
	if(tr[0][c]) q.push(tr[0][c]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int c=0;c<=1;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[tr[x][c]]=tr[Next[x]][c];
				q.push(tr[x][c]);
			}
		}
	}
}
int get(int x)
{
	if(!x) return -1;
	if(End[x]) return x;
	if(pre[x]) return pre[x];
	return pre[x]=get(Next[x]);
}
void GetPre()
{
	for(int i=0;i<=tot;i++)
	pre[i]=-1;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();
		if(pre[x]==-1) pre[x]=get(Next[x]);
		q.pop();
		for(int c=0;c<=1;c++)
		{
			int y=tr[x][c];
			if(!vis[y])
			{
				vis[y]=1;
				q.push(y);
			}
		}
	}
}
bool d[M][M];
void Substring(int x)
{
	int p=0;
	for(int i=St[x];i<=Ed[x];i++)
	{
		int c=S[i];
		p=tr[p][c];
		int l=(End[p]?p:pre[p]);
		while(l&&l!=-1&&End[l]==x)
		l=pre[l];
		if(l!=-1&&l)
		{
			d[x][End[l]]=1;
		}
	}
}
void GetSub()
{
	for(int i=1;i<=n;i++)
	Substring(i);
}
int ins[M],match[M];
int tag=0;
struct edge
{
	int y,next;
}e[M*M];
int link[M],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
int pos[M],A[M],B[M];
bool dfs(int x)
{
	if(ins[x]==tag) return 0;
	ins[x]=tag;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(!match[y]||dfs(match[y]))
		{
			match[y]=x;
			pos[x]=y;
			return 1;
		}
	} 
	return 0;
}
void mark(int x)
{
	if(A[x]) return;
	A[x]=1;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(!B[y])
		{
			B[y]=1;
			mark(match[y]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	Insert(i);
	GetNxt();
	GetPre();
	GetSub();
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	d[i][j]|=(d[i][k]&d[k][j]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(i==j) continue;
		if(d[i][j]) add(i,j);
	}
	int ans=n;
	for(int i=1;i<=n;i++)
	{
		tag++;
		ans-=(int)dfs(i);
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
	if(!pos[i]) mark(i);
	for(int i=1;i<=n;i++)
	if(A[i]&&!B[i]) printf("%d ",i);
 	return 0;
}

CF587F Duff is Mad

对串长根号分治，

若$s_k$长度大于根号，那么可以对每个$k$分别做。

把$s_k$经过的点权值加一，那么一个串的出现次数就是子树和。

可以提前预处理一下。

差分一下再扫描线就好了。

小于根号的话，我们把答案拆成两个的差，然后扫描n个串，给每个串的子树加，询问暴力遍历就好了。

用分块平衡复杂度可以做到
$O(n\sqrt{n})$

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
const int S = 400;
typedef long long LL;
int tr[N][27],Next[N];
vector<int> str[N];
int len[N],End[N];
int tot=0;
void Insert(int x)
{
	int p=0;
	for(int i=1;i<=len[x];i++)
	{
		int c=str[x][i];
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	}
	End[x]=p;
}
queue<int> q;
void Build()
{
	for(int c=0;c<26;c++)
	if(tr[0][c]) q.push(tr[0][c]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int c=0;c<26;c++)
		{
			int y=tr[x][c];
			if(!y) tr[x][c]=tr[Next[x]][c];
			else
			{
				Next[y]=tr[Next[x]][c];
				q.push(y);
			}
		}
	}
}
int n,m;
char s[N];
int B;
struct Query
{
	int x,tp,id;
};
vector<Query> Q1[N],Q2[N];
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
int st[N],ed[N],siz[N];
int top=0;
int seq[N];
void dfs(int x)
{
	siz[x]=1;
	st[x]=++top;
	seq[top]=x;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		dfs(y);
		siz[x]+=siz[y];
	}
	ed[x]=top;
}
int L[N],R[N],cnt=0;
int bel[N];
LL a[N],tag[N];
void Blocks()
{
	for(int i=1;i<=tot+1;i++)
	{
		bel[i]=(i-1)/B+1;
		R[bel[i]]=i;
		if(!L[bel[i]]) L[bel[i]]=i;
		cnt=max(cnt,bel[i]);
	}
}
void Add(int l,int r,int v)
{
	if(bel[r]-bel[l]<=1)
	{
		for(int i=l;i<=r;i++)
		a[i]+=v;
		return;
	}
	else
	{
		for(int i=l;i<=R[bel[l]];i++) a[i]+=v;
		for(int i=L[bel[r]];i<=r;i++) a[i]+=v;
		for(int i=bel[l]+1;i<bel[r];i++) tag[i]+=v;
		return; 
	}
}
LL Ans[N];
bool cmp(Query a,Query b)
{
	return a.x<b.x;
}
int main()
{
	cin>>n>>m;
	for(int x=1;x<=n;x++)
	{
		scanf("%s",s+1);
		str[x].push_back(0);
		len[x]=strlen(s+1);
		for(int i=1;i<=len[x];i++)
		str[x].push_back(s[i]-'a');
		Insert(x);
	}
	Build();
	B=sqrt(tot*1.0+1);
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		scanf("%d %d %d",&l,&r,&x);
		if(len[x]>B)
		{
			if(l!=1) Q2[x].push_back((Query){l-1,-1,i});
			Q2[x].push_back((Query){r,1,i});
		}
		else
		{
			if(l!=1) Q1[l-1].push_back((Query){x,-1,i});
			Q1[r].push_back((Query){x,1,i});
		}
	}
	for(int i=1;i<=tot;i++)
	add(Next[i],i);
	dfs(0);
	Blocks();
	for(int i=1;i<=n;i++)
	{
		Add(st[End[i]],ed[End[i]],1);
		for(int p=0;p<(int)Q1[i].size();p++)
		{
			int x=Q1[i][p].x,tp=Q1[i][p].tp,id=Q1[i][p].id;
			int r=0;
			for(int j=1;j<=len[x];j++)
			{
				int c=str[x][j];
				r=tr[r][c];
				Ans[id]+=1ll*(a[st[r]]+tag[bel[st[r]]])*tp;
			} 
		}
	}
	for(int x=1;x<=n;x++)
	{
		if(Q2[x].size())
		{
			memset(a,0,sizeof(a));
			int p=0;
			for(int i=1;i<=len[x];i++)
			{
				int c=str[x][i];
				p=tr[p][c];
				a[p]++;
			}
			sort(Q2[x].begin(),Q2[x].end(),cmp);
			for(int i=top;i>=2;i--)
			a[Next[seq[i]]]+=a[seq[i]];		
			int j=1;
			LL sum=0;
			for(p=0;p<(int)Q2[x].size();p++)
			{
				int y=Q2[x][p].x;
				while(j<=y)  sum+=a[End[j++]];
				Ans[Q2[x][p].id]+=1ll*sum*Q2[x][p].tp;
			}
		}
	}
	for(int i=1;i<=m;i++)
	printf("%lld\n",Ans[i]);
	return 0;
} 

其他题目

CF1110H Modest Substrings

P5599 【XR-4】文本编辑器

CF1483F Exam

[BJOI2016]打字机

P3735 [HAOI2017]字符串