【JZOJ6216】【20190614】序列计数

题目

一个长为$N$的串$S$，$M$询问区间$[l,r]$不同的子串个数，字符集为$ C $

$N ,M \le 10^5 \ , \ C \le 10$

题解

这题非常套路。。。
part 1
设$dp_{i,j}$为考虑i，字符j结尾的子串个数，考虑$S_i=c$

\[\begin{align}
&dp_{i,j} = dp_{i,j}\\
&dp_{i,c} = \sum_{j} dp_{i-1,j} + 1
\end{align}
\]
part 2
设一个大小$C+1$的矩阵，写出转移矩阵

\[A_i = \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
1 & 1 & 1 & 1\\
0 & 0 & 0 & 1\\
\end{pmatrix}
\]

它的逆矩阵

\[B_i = \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
-1 & -1 & -1 & -1\\
0 & 0 & 0 & 1\\
\end{pmatrix}
\]

只需要预处理出矩阵的前缀即可
part 3

左乘一个A相当于某一行变为所有行的和，可以维护一列的和

右乘一个B相当于其它列减去某一列，可以维护整体减法标记

统计答案也可以直接利用维护的东西，具体见代码

时间复杂度$ O((N+M)C) $

#include<bits/stdc++.h>

using namespace std;

const int N=500010,mod=1e9+7;

int n,m,f1[N][11],f2[N][11];

char s[N],ps[1000000],*pp=ps;

void flush(){fwrite(ps,1,pp-ps,stdout);pp=ps;}

void push(char x){if(pp==ps+1000000)flush();*pp++=x;}

void write(int x){

	static int sta[20],top;

	if(!x){push('0');push('\n');return;}

	while(x)sta[++top]=x%10,x/=10;

	while(top)push(sta[top--]^'0');

	push('\n');

}

void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}

void dec(int&x,int y){x-=y;if(x<0)x+=mod;}

struct Mat{

	int c[11][11],s[11],d[11],D;

	void init(){for(int i=0;i<11;++i)c[i][i]=s[i]=1;}

	void plus(int I){

		for(int i=0;i<11;++i){

			int t=c[I][i];c[I][i]=s[i];

			s[i]=(2*s[i]%mod-t+mod)%mod;

		}

	}

	void minus(int I){

		for(int i=0;i<11;++i){

			int t=d[i];d[i]=c[i][I];

			c[i][I]=(2*d[i]%mod-t+mod)%mod;

		}

	}

	void print(int typ){

		for(int i=0;i<11;++i,puts(""))

		for(int j=0;j<11;++j){

			int t=typ?(c[i][j]-d[i]+mod)%mod:c[i][j];

			if(mod-t<t)t=t-mod;

			printf("% 2d ",t);

		}

		puts("\n");

		if(!typ)for(int i=0;i<11;++i)printf("%d ",s[i]);

		puts("\n");

	}

}A,B;

int main(){

	freopen("sequence.in","r",stdin);

	freopen("sequence.out","w",stdout);

	scanf("%s%d",s+1,&m);n=strlen(s+1);

	A.init(),B.init();f2[0][10]=1;

	for(int i=1;i<=n;++i){

		A.plus(s[i]-'a');

		B.minus(s[i]-'a');

		for(int j=0;j<11;++j){

			f1[i][j]=A.s[j];

			f2[i][j]=(B.c[j][10]-B.d[j]+mod)%mod;

		}

	}

	for(int i=1,l,r,ans;i<=m;++i){

		scanf("%d%d",&l,&r);

		ans=0;for(int j=0;j<11;++j)inc(ans,1ll*f1[r][j]*f2[l-1][j]%mod);

		if(!ans)ans=mod-1;else ans--;write(ans);

	}

	return flush(),0;

}

巴特西

【JZOJ6216】【20190614】序列计数

题目

题解

最新文章

热门文章