思路
首先考虑暴力(dp)
用(f[i][j])表示前(i)个字符,以(j)这个字符结尾的本质不同的字符串个数。
然后就有如下的转移
(if(s_i==j))
$$f_{ij}=sumlimits_{i=1}^9f_{i-1j} + 1$$
(else)
$$f_{ij}=f_{i-1j}$$
然后就尝试一下用矩阵转移
对于第(i)位置，设一个(10 imes 10)的单位矩阵，将(s_i)这一列全都是(1)。
为什么是(10 imes 10)而不是(9 imes9)呢？
因为第一个转移里面有个(+1)
然后对于每次询问，都将初始的(1 imes 10)的矩阵的第(s_{l-1})位和第(10)位设成(1)，其他的都是(0)。
然后依次乘上(l)~(r)的矩阵即可。
然后优化
可以发现，用矩阵转移更慢了。
别慌，我们只要想办法快速的将(l)~(r)内的矩阵乘起来不就行了。
对于这(n)个矩阵先处理一个前缀和。然后只要用前(r)个矩阵去除以前(l - 1)个矩阵就行了。
怎么除呢？？
我们把每个矩阵的逆矩阵也求个前缀和就行了。
PS： 矩阵乘法不满足交换律，注意矩阵相乘的顺序。
代码
/* @Author: wxyww
* @Date: 2019-03-28 20:43:54
* @Last Modified time: 2019-03-29 13:53:49
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010,mod = 1e9 + 7;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int a[11][11];
int n,m;
node() {
memset(a,0,sizeof(a));
}
node(int x) {
n = m = x;
memset(a,0,sizeof(a));
for(int i = 1;i <= x;++i) a[i][i] = 1;
}
node(int x,int y) {
n = x,m = y;
memset(a,0,sizeof(a));
}
}tmp1[N],tmp2[N];
char S[N];
int n,s[N];
node operator * (const node &A,const node &B) {
int n = A.n,m = B.n,K = A.m;
node ret(n,m);
for(int k = 1;k <= K;++k) {
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
ret.a[i][j] += 1ll * A.a[i][k] * B.a[k][j] % mod;
ret.a[i][j] %= mod;
}
}
}
return ret;
}
void pre() {
tmp1[0] = tmp2[0] = node(10);
for(int i = 1;i <= n;++i) {
int k = s[i];
tmp1[i] = tmp2[i] = node(10);
for(int j = 1;j <= 10;++j) tmp1[i].a[j][k] = 1,tmp2[i].a[j][k] = mod - 1;
tmp2[i].a[k][k] = 1;
tmp1[i] = tmp1[i] * tmp1[i - 1];
tmp2[i] = tmp2[i - 1] * tmp2[i];
}
}
int main() {
scanf("%s",S + 1);
n = strlen(S + 1);
for(int i = 1;i <= n;++i) s[i] = S[i] - 'a' + 1;
pre();
int m = read();
while(m--) {
node ans(1,10);
int l = read(),r = read();
ans.a[1][10] = 1;
ans = ans * tmp1[r] * tmp2[l - 1];
int anss = 0;
for(int i = 1;i <= 9;++i) anss += ans.a[1][i],anss %= mod;
printf("%d
",anss);
}
return 0;
}
*/