[LOJ6074 2017 山东一轮集训 Day6]子序列

对于一个区间考虑如何dp。

在每一个位置钦定转移到某种字符上,并且走到最近的这种字符,相当于建出了一个DAG,可以统计本质不同的子序列。

latex f_{i,j} 表示在第 latex i 位上,钦定转移到字符 latex j 的方案数,那么从 latex ilatex i+1 时,仅有 latex f_{i+1,s_i}latex f_i 不同。

因为根据定义,只有 latex s_i 的转移发生了变化。

而且转移可以写成矩阵的形式,转移矩阵只有 latex s_i 这一行和对角线是 latex 1,并且可以得到它的逆矩阵。

那么预处理转移矩阵前缀积和逆矩阵前缀积即可。

但是这样复杂度有点高,矩阵有特殊性质,一次转移相当于把 latex s_i 这一行变成之前所有行的和。逆矩阵类似。

那么矩乘的复杂度就只有 latex n^2 了,实际上只需要额外维护一个矩阵每一列的和,就可以做到 latex O(n) 的矩乘。

复杂度 latex O(10n+10q)

#include <bits/stdc++.h>
using namespace std;
int read() {
	int x = 0, f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}

const int MaxN = 100033;
const int MaxM = 11;
const int mod = 1000000007;

int n, m, q;
inline void Add(int &a, int b) {
	a = (a + b) % mod;
}
inline void Dec(int &a, int b) {
	a = (a - b) % mod;
}

char str[MaxN];
int s[MaxN];
int f1[MaxN][MaxM], f2[MaxN][MaxM];
int g1[MaxM][MaxM], g2[MaxM][MaxM];
void solve() {
	for (int i = 0; i <= m; i++) {
		memset(g1[i], 0, sizeof g1[i]);
		memset(g2[i], 0, sizeof g2[i]);
		g1[i][i] = g2[i][i] = f1[0][i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			f1[i][j] = (f1[i - 1][j] * 2 % mod - g1[s[i]][j]) % mod;
			g1[s[i]][j] = f1[i - 1][j];
			f2[i][j] = g2[s[i]][j];
			g2[s[i]][j] = (g2[s[i]][j] * 2 % mod - f2[i - 1][j]) % mod;
		}
	}
}

int main() {
	m = 9;
	scanf("%s", str + 1), n = strlen(str + 1);
	for (int i = 1; i <= n; i++)
		s[i] = str[i] - 'a';
	solve();
	q = read();
	while (q--) {
		int l = read(), r = read(), ans = 0;
		ans = f1[r][m];
		for (int i = 0; i <= m; i++)
			Dec(ans, 1ll * f2[l - 1][i] * f1[r][i] % mod);
		printf("%d\n", (ans + mod - 1) % mod);
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注