题目描述
题解
对于子序列的dp，我们可以设置一个dp。
我们设dp[i]表示以i这个字符结尾的子序列个数，转移为dp[i]+=∑dp[k]-dp[i]。其实我们发现这样等价于dp[i]=∑dp[k]。
另外我们还要再设一个空字符的位置表示空字符，所以我们的转移矩阵长成这样。
1 0 1 0 0
0 1 1 0 0
0 0 1 0 0
0 0 1 1 0
0 0 1 0 1
我们一开始是空的，所以转移矩阵为
0 0 0 0 1
最后我们要归为一个答案，所以还要乘上一个列矩阵。
1
1
1
1
0
直接做是N^3的，我们发现这个矩阵长得非常有特点，我们把它的逆矩阵求出来之后发现。
1 0 -1 0 0
0 1 -1 0 0
0 0 1 0 0
0 0 -1 1 0
0 0 -1 0 1
所以我们的思路就是让行向量*1~l-1的逆矩阵再乘上1~r的正矩阵，在乘上列矩阵。
对于正矩阵和逆矩阵的部分我们可以分开维护。
对于正矩阵的右乘的过程，我们可以维护每一行的和，因为每次的乘法相当于把ch位变成这一行的和，所以就直接维护就好了。
注意我们维护的是最后做完之后再乘上一个列矩阵，所以维护的时候只需要维护矩阵和矩阵乘列向量的值就好了。
对于逆矩阵的左乘，我们考虑它实际上是把当前列的第ch位减掉，而且它是对每个列除了ch行都批量的减掉，所以我们维护一下每一列的加法标记就好了。
同样我们也是要维护乘完之后再去乘上行向量的答案。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 11
#define N 100002
using namespace std;
const int mod=1e9+;
char s[N];
int sum[M],n,c,now[M][M],val[N],nowl[N][M],nowr[N][M],tag[M];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
int main(){
scanf("%s",s+);n=strlen(s+);
c=;
for(int i=;i<=c;++i)sum[i]=,nowr[][i]=,now[i][i]=;
nowr[][c]=;
for(int i=;i<=n;++i){
int x=s[i]-'a';
for(int j=;j<=c;++j)
val[j]=now[j][x],now[j][x]=sum[j];
for(int j=;j<=c;++j)sum[j]=(1ll*sum[j]*-val[j]+mod)%mod;
for(int j=;j<=c;++j)nowr[i][j]=(1ll*sum[j]-now[j][c]+mod)%mod;
}
nowl[][c]=;
memset(now,,sizeof(now));
for(int i=;i<=c;++i)now[i][i]=;
for(int i=;i<=n;++i){
int x=s[i]-'a';
for(int j=;j<=c;++j)val[j]=(now[x][j]+tag[j])%mod;
for(int j=;j<=c;++j)now[x][j]=(now[x][j]+val[j])%mod,tag[j]=(tag[j]-val[j]+mod)%mod;
for(int j=;j<=c;++j)nowl[i][j]=(now[c][j]+tag[j])%mod;
}
int q=rd();int l,r;
while(q--){
l=rd();r=rd();int ans=;
for(int i=;i<=c;++i)(ans+=1ll*nowr[r][i]*nowl[l-][i]%mod)%=mod;
printf("%d\n",ans);
}
return ;
}