c/c++开发分享loj6074子序列

首先考虑暴力(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 times 10)的单位矩阵，将(s_i)这一列全都是(1)。

为什么是(10 times 10)而不是(9times9)呢？

因为第一个转移里面有个(+1)

然后对于每次询问，都将初始的(1 times 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 #include #include #include #include #include #include #include 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<&＃39;0&＃39;||c>&＃39;9&＃39;) {         if(c==&＃39;-&＃39;) f=-1;         c=getchar();     }     while(c>=&＃39;0&＃39;&&c<=&＃39;9&＃39;) {         x=x*10+c-&＃39;0&＃39;;         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] - &＃39;a&＃39; + 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("%dn",anss);     }     return 0; }  */