# 后端 「LOJ 6074」「2017 山东一轮集训 Day6」子序列

rightpalmprint · December 10, 2019 · 27 hits

LOJ 6074

## 题解

[dp_{i,j}=begin{cases}dp_{i-1,j} & text{ if } jne S_i \\ sum_{k=0}^{m} dp_{i-1,k} & text{ if }j=S_iend{cases}]

[F_i=begin{pmatrix}dp_{i,0} & dp_{i,1} & dp_{i,2} & cdots & dp_{i,m}end{pmatrix}]

[begin{aligned}M_i &= begin{pmatrix}1 & & 1 & & \\ & 1 & 1 & & \\ & & 1 & & \\ & & vdots & ddots & \\ & & 1 & & 1 end{pmatrix} \\ F_i &= F_{i-1}M_iend{aligned}]

(M_i) 是一个主对角线为 (1)(S_i) 这一列为 (1)，其余为 (0) 的矩阵。

[A=begin{pmatrix}0 & 0 & 0 & cdots & 0 & 1end{pmatrix}]

[left(sum_{i=0}^m dp_{n,i}right)-1]

[B=begin{pmatrix}1 \\ 1 \\ 1 \\ vdots \\ 1end{pmatrix}]

[begin{aligned}ans&=AM_lM_{l+1}M_{l+2}cdots M_{r}B\\&=AM_{l-1}^{-1}M_{l-2}^{-1}cdots M_1^{-1}M_1M_2cdots M_{r}Bend{aligned}]

[begin{aligned}CM_i&=begin{pmatrix}C_{0,0} & C_{0,1} & C_{0,2} & cdots & C_{0,m} \\ C_{1,0} & C_{1,1} & C_{1,2} & cdots & C_{1,m} \\ C_{2,0} & C_{2,1} & C_{2,2} & cdots & C_{2,m} \\ & & & ddots & \\ C_{m,0} & C_{m,1} & C_{m,2} & cdots & C_{m,m} end{pmatrix}begin{pmatrix}1 & & 1 & & \\ & 1 & 1 & & \\ & & 1 & & \\ & & vdots & ddots & \\ & & 1 & & 1 end{pmatrix} \\ &= begin{pmatrix}C_{0,0} & C_{0,1} & sum_{j=0}^m C_{0,j} & cdots & C_{0,m} \\ C_{1,0} & C_{1,1} & sum_{j=0}^m C_{1,j} & cdots & C_{1,m} \\ C_{2,0} & C_{2,1} & sum_{j=0}^m C_{2,j} & cdots & C_{2,m} \\ & & & ddots & \\ C_{m,0} & C_{m,1} & sum_{j=0}^m C_{m,j} & cdots & C_{m,m} end{pmatrix}end{aligned}]

[M_i^{-1}=begin{pmatrix}1 & & -1 & & \\ & 1 & -1 & & \\ & & 1 & & \\ & & vdots & ddots & \\ & & -1 & & 1 end{pmatrix}]

(M_i^{-1}) 是主对角线为 (1)，第 (S_i) 列除了第 (S_i) 行外是 (-1) 的矩阵。

[begin{aligned}M_i^{-1}C&=begin{pmatrix}1 & & -1 & & \\ & 1 & -1 & & \\ & & 1 & & \\ & & vdots & ddots & \\ & & -1 & & 1 end{pmatrix}begin{pmatrix}C_{0,0} & C_{0,1} & C_{0,2} & cdots & C_{0,m} \\ C_{1,0} & C_{1,1} & C_{1,2} & cdots & C_{1,m} \\ C_{2,0} & C_{2,1} & C_{2,2} & cdots & C_{2,m} \\ & & & ddots & \\ C_{m,0} & C_{m,1} & C_{m,2} & cdots & C_{m,m} end{pmatrix} \\ &= begin{pmatrix}C_{0,0}-C_{2,0} & C_{0,1}-C_{2,1} & C_{0,2}-C_{2,2} & cdots & C_{0,m}-C_{2,m} \\ C_{1,0}-C_{2,0} & C_{1,1}-C_{2,1} & C_{1,2}-C_{2,2} & cdots & C_{1,m}-C_{2,m} \\ C_{2,0} & C_{2,1} & C_{2,2} & cdots & C_{2,m} \\ & & & ddots & \\ C_{m,0}-C_{2,0} & C_{m,1}-C_{2,1} & C_{m,2}-C_{2,2} & cdots & C_{m,m}-C_{2,m} end{pmatrix}end{aligned}]

[begin{pmatrix}x_0-v \\ x_1-v \\ x_2-v \\ vdots \\ x_m-v end{pmatrix}]

[begin{pmatrix}x_0-v-(x_2-v) \\ x_1-v-(x_2-v) \\ x_2-v \\ vdots \\ x_m-v-(x_2-v) end{pmatrix}==begin{pmatrix}x_0-x_2 \\ x_1-x_2 \\ (2x_2-v)-x_2 \\ vdots \\ x_m-x_2 end{pmatrix}]

[begin{pmatrix}0 & 0 & 0 & cdots & 0 & 1end{pmatrix}]

## 代码

 `12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849` `#include #include #include int (){ register int x = 0; register char f = 1, ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') f ^= 1; for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return f ? x : -x;}#define N 100005#define P 1000000007int n, q, a[10][10], av[10][10], f[N][10], fv[N][10];char s[N];int plus(int a, int b){ return (a += b) >= P ? a - P : a;}int minus(int a, int b){ return (a -= b) < 0 ? a + P : a;}void init(int n){ for (register int i = 0; i <= 9; ++i) a[i][i] = av[i][i] = f[0][i] = 1; for (register int i = 1; i <= n; ++i){ int t = s[i] - 'a'; for (register int j = 0; j <= 9; ++j){ f[i][j] = plus(minus(f[i - 1][j], a[j][t]), f[i - 1][j]); a[j][t] = f[i - 1][j]; fv[i][j] = av[t][j]; av[t][j] = minus(plus(av[t][j], av[t][j]), fv[i - 1][j]); } } for (register int i = 0; i <= n; ++i) for (register int j = 0; j <= 9; ++j) fv[i][j] = minus(j == 9, fv[i][j]);}int main(){ while (islower(s[++n] = getchar())) ; --n; init(n); q = read(); while (q--){ int l = read(), r = read(), ans = 0; for (register int i = 0; i <= 9; ++i) ans = plus(ans, 1ll * fv[l - 1][i] * f[r][i] % P); printf("%dn", minus(ans, 1)); }}`