Description
n,q<=1e5
Solution
迟来的总结 比赛时只会O(n)Dp离线搞了60分 这个就是F[i]=2*F[i-1]-F[next[i]-1] 其中next[i]表示i前面第一个和i字符相同的位置
正解的Dp长这样： 设s[i]=c，则F[i][c]=∑F[i-1][k],F[i][k]=F[i-1][k] 然后这样可以写成一个转移矩阵，并且是有逆矩阵的 所以我们可以预处理转移矩阵的前缀积和逆矩阵的倒过来的前缀积 那么询问直接用这两个相乘就好了
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=
1e5+
5,mo=
1e9+
7;
int a[
10][
10][
10],b[
10][
10][
10],c[
10][
10],d[
10][
10],f[
10],an[
10];
int n,m,l,r,pre[N][
10][
10],suf[N][
10][
10];
char st[N];
int read() {
char ch;
for(ch=getchar();ch<
'0'||ch>
'9';ch=getchar());
int x=ch-
'0';
for(ch=getchar();ch>=
'0'&&ch<=
'9';ch=getchar()) x=x*
10+ch-
'0';
return x;
}
int mi(
int x,
int y) {
int z=
1;
for(;y;y/=
2,x=(ll)x*x%mo)
if (y&
1) z=(ll)z*x%mo;
return z;
}
void get_ni(
int x) {
fo(i,
0,
9) b[x][i][i]=
1;
fo(i,
0,
8) {
fo(j,i+
1,
9)
if (c[j][i]>c[i][i])
fo(k,i,
9) {
swap(c[j][k],c[i][k]);
swap(b[x][j][k],b[x][i][k]);
}
int ni=mi(c[i][i],mo-
2);
fo(j,i+
1,
9) {
int t=(ll)c[j][i]*ni%mo;
fo(k,i,
9) {
(c[j][k]+=mo-(ll)c[i][k]*t%mo)%=mo;
(b[x][j][k]+=mo-(ll)b[x][i][k]*t%mo)%=mo;
}
}
}
fd(i,
9,
1) {
int ni=mi(c[i][i],mo-
2);
fo(j,
0,i-
1) {
int t=(ll)c[j][i]*ni%mo;
fo(k,i,
9) {
(c[j][k]+=mo-(ll)c[i][k]*t%mo)%=mo;
(b[x][j][k]+=mo-(ll)b[x][i][k]*t%mo)%=mo;
}
}
}
}
int main() {
freopen(
"sub.in",
"r",stdin);
freopen(
"sub.out",
"w",stdout);
fo(i,
0,
8) {
fo(j,
0,
9) {
a[i][j][j]=
1;
a[i][j][i]=
1;
}
memcpy(c,a[i],
sizeof(c));
get_ni(i);
}
scanf(
"%s",st+
1);n=
strlen(st+
1);
fo(i,
0,
9) pre[
0][i][i]=suf[
0][i][i]=
1;
fo(w,
1,n) {
int x=st[w]-
'a';
memset(d,
0,
sizeof(d));
fo(k,
0,
9)
fo(i,
0,
9)
fo(j,
0,
9)
(d[i][j]+=(ll)pre[w-
1][i][k]*a[x][k][j]%mo)%=mo;
memcpy(pre[w],d,
sizeof(d));
memset(d,
0,
sizeof(d));
fo(k,
0,
9)
fo(i,
0,
9)
fo(j,
0,
9)
(d[i][j]+=(ll)b[x][i][k]*suf[w-
1][k][j]%mo)%=mo;
memcpy(suf[w],d,
sizeof(d));
}
for(m=read();m;m--) {
l=read();r=read();
memset(f,
0,
sizeof(f));
memset(an,
0,
sizeof(an));
f[
9]=
1;
fo(i,
0,
9)
fo(j,
0,
9)
(an[j]+=(ll)f[i]*suf[l-
1][i][j]%mo)%=mo;
memcpy(f,an,
sizeof(f));
memset(an,
0,
sizeof(an));
fo(i,
0,
9)
fo(j,
0,
9)
(an[j]+=(ll)f[i]*pre[r][i][j]%mo)%=mo;
int ans=
0;
fo(i,
0,
8) (ans+=an[i])%=mo;
printf(
"%d\n",ans);
}
}
