美趣,花药满田,05j909
首先考虑暴力\(dp\)
用\(f[i][j]\)表示前\(i\)个字符,以\(j\)这个字符结尾的本质不同的字符串个数。
然后就有如下的转移
\(if(s_i==j)\)
\[f_{ij}=\sum\limits_{i=1}^9f_{i-1j} + 1\]
\(else\)
\[f_{ij}=f_{i-1j}\]
然后就尝试一下用矩阵转移
对于第\(i\)位置，设一个\(10 \times 10\)的单位矩阵，将\(s_i\)这一列全都是\(1\)。
为什么是\(10 \times 10\)而不是\(9\times9\)呢？
因为第一个转移里面有个\(+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<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\n",anss);
}
return 0;
}
*/
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论