〇#

子序列：对于一个给定序列，按原本顺序抽取若干元素，构成的序列即为序列的子序列。

本质不同：对于两个子序列 $\{b_n\}$ 和 $\{c_n\}$ ，若其元素个数不同或存在 $b_i\neq c_i$ ，则称它们是本质不同的。

本质不同子序列：要求子序列必须是非空的。

对于两个子序列 $a,b$ ， $a+b$ 表示将 $a$ 和 $b$ 首尾相连，构成一个新的子序列。

一#

给定长度为 $n$ 的序列 $\{a_n\}$ ，求在 $\{a_n\}$ 中有多少个本质不同的子序列。

考虑设 $f_i$ 表示截至第 $i$ 个数，有多少个本质不同子序列；设 $\operatorname{last}_{i}$ 表示数值 $i$ 的上一次出现位置，初始值为 $0$ ，在遍历更新 $f$ 时随时更新。

则有转移方程：

f_i=\left\{ \begin{array}{lr} 2\times f_{i-1}+1, &\operatorname{last}_{a_i}=0\\ 2\times f_{i-1} - f_{\operatorname{last}_{a_i} - 1}, &\operatorname{last}_{a_i}\neq0\\ \end{array} \right.

理解：

若之前从未出现过 $a_i$ ，对任意之前出现过的子序列 $s$ ， $s+a_i$ 都是新的子序列；另外， $a_i$ 本身也可以作为一个新的子序列。
若之前出现过 $a_i$ ，对于一个仅包含 $\operatorname{last}_i$ 之前的元素的子序列 $s$ ， $s+i$ 已经被计算过了，容斥减去。

二#

给定长度为 $n$ 的 01 序列 $\{a_n\}$ ，求在 $\{a_n\}$ 中有多少个本质不同的子序列。

时间复杂度 $\mathcal{O}(n)$ .

考虑设 $f_{i,0/1}$ 表示截至第 $i$ 个数，有多少以 $0/1$ 结尾的本质不同子序列。

则有转移方程：

f_{i,0}=\left\{ \begin{array}{lr} f_{i-1,0}+f_{i-1,1}+1, &a_i=0\\ f_{i-1,0}, & a_i=1\\ \end{array} \right.

f_{i,1}=\left\{ \begin{array}{lr} f_{i-1,1}, &a_i=0\\ f_{i-1,0}+f_{i-1,1}+1, & a_i=1\\ \end{array} \right.

理解：

若当前位置 $a_i=1$ ，考虑以 $1$ 结尾的子序列。对于 $f_{i-1}$ 包含的所有本质不同子序列，都直接在后面添上一个 $1$ ，这些子序列依然不重不漏，除此之外，以 $1$ 结尾的子串还可以为单独的一个 $1$ 。

对于由 $0$ 结尾的子序列， $a_i$ 不能造成任何贡献。

由此，此时 $f_{i,1}=f_{i-1,0}+f_{i-1,1}+1$ ， $f_{i,0}=f_{i-1,0}$ .

三#

给定长度为 $n$ 的 01 序列 $\{a_n\}$ ， $m$ 次询问子段 $a_l\sim a_r$ 中有多少个本质不同的子序列。

时间复杂度 $\mathcal{O}(m)\sim \mathcal{O}(m\log n)$ .

在二的基础上，注意到转移只与 $f_{i-1}$ 有关，因此可以构造 $3\times 3$ 的矩阵，用矩阵快速幂优化。

若 $a_i=0$ ，

\begin{bmatrix} f_{i-1,1}& f_{i-1,0} &1\end{bmatrix}\times \begin{bmatrix} 1 &1 &0\\ 0 &1 &0\\ 0 &1 &1\\ \end{bmatrix}= \begin{bmatrix} f_{i,1}& f_{i,0} &1\end{bmatrix}

若 $a_i=1$ ，

\begin{bmatrix} f_{i-1,1}& f_{i-1,0} &1\end{bmatrix}\times \begin{bmatrix} 1 &0 &0\\ 1 &1 &0\\ 1 &0 &1\\ \end{bmatrix}= \begin{bmatrix} f_{i,1}& f_{i,0} &1\end{bmatrix}

形式化地，设 $M_0=\begin{bmatrix}1 &1 &0\\0 &1 &0\\0 &1 &1\\\end{bmatrix}$ ， $M_1=\begin{bmatrix}1 &0 &0\\1 &1 &0\\1 &0 &1\\\end{bmatrix}$ ，则答案矩阵为 $\prod\limits_{i=l}^rM_{a_i}$ .

可以预处理逆矩阵，用前缀积进一步优化。

四#

给定长度为 $n$ 的 01 序列 $\{a_n\}$ ， $m$ 次询问操作：

把数列子段 $a_l\sim a_r$ 中的所有数取反。
求数列子段 $a_l\sim a_r$ 中有多少个本质不同的子序列。

时间复杂度 $\mathcal{O}(m\log n)$ .

观察可知，区间翻转等价于交换 $3\times 3$ 矩阵的前两列。

用线段树维护区间矩阵乘积，懒标记维护区间翻转操作。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int ret = 0, ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch <= '9' && ch >= '0') {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret;
}
const int MAXN = 1e5 + 10, mod = 1e9 + 7;
int n, m, a[MAXN], f[MAXN];
//dp[i][1] = dp[i-1][1] + dp[i-1][0] + 1, dp[i][0] = dp[i-1][0], a[i]=1
//dp[i][1] = dp[i-1][1], dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1, a[i]=0
struct Matrix{
	int n, m, a[4][4];
	Matrix() { memset(a, 0, sizeof(a)); }
	friend Matrix operator * (const Matrix &A, const Matrix &B) {
		Matrix C;
		C.n = A.n, C.m = B.m;
		for(int i = 1; i <= C.n; i++) {
			for(int j = 1; j <= C.m; j++) {
				for(int k = 1; k <= A.m; k++) {
					C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
				}
			}
		}
		return C;
	}
	inline void rev() {
		for(int i = 1; i <= 3; i++) swap(a[i][1], a[i][2]);
		for(int i = 1; i <= 3; i++) swap(a[1][i], a[2][i]);
	}
} M[2];
inline Matrix unit(int n) {
	Matrix R; R.n = R.m = n;
	for(int i = 1; i <= n; i++) R.a[i][i] = 1;
	return R;
}
inline void Init_M() {
	M[0].n = M[0].m = M[1].n = M[1].m = 3;
	M[0].a[1][1] = 1, M[0].a[1][2] = 1, M[0].a[1][3] = 0;
	M[0].a[2][1] = 0, M[0].a[2][2] = 1, M[0].a[2][3] = 0;
	M[0].a[3][1] = 0, M[0].a[3][2] = 1, M[0].a[3][3] = 1;
	M[1].a[1][1] = 1, M[1].a[1][2] = 0, M[1].a[1][3] = 0;
	M[1].a[2][1] = 1, M[1].a[2][2] = 1, M[1].a[2][3] = 0;
	M[1].a[3][1] = 1, M[1].a[3][2] = 0, M[1].a[3][3] = 1;
}
Matrix t[MAXN << 2]; int tag[MAXN << 2], lc[MAXN << 2], rc[MAXN << 2];
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
inline void push_up(int id) { t[id] = t[ls(id)] * t[rs(id)]; }
inline void push_down(int id) {
	if(!tag[id]) return ;
	t[ls(id)].rev(), t[rs(id)].rev();
	tag[ls(id)] ^= 1, tag[rs(id)] ^= 1;
	tag[id] = 0;
}
void build(int id, int l, int r) {
	tag[id] = 0;
	lc[id] = l; rc[id] = r;
	if(l == r) {
		t[id] = M[a[l] == 1];
		return ;
	}
	int mid = (l + r) >> 1;
	build(ls(id), l, mid);
	build(rs(id), mid + 1, r);
	push_up(id);
}
void update(int id, int l, int r, int X, int Y) {
	if(X <= l && r <= Y) {
		tag[id] ^= 1;
		t[id].rev();
		return;
	}
	push_down(id);
	int mid = (l + r) >> 1;
	if(X <= mid) update(ls(id), l, mid, X, Y);
	if(Y > mid) update(rs(id), mid + 1, r, X, Y);
	push_up(id);
}
Matrix query(int id, int l, int r, int X, int Y) {
	if(X <= l && r <= Y) return t[id];
	push_down(id);
	int mid = (l + r) >> 1; Matrix ret = unit(3);
	if(X <= mid) ret = ret * query(ls(id), l, mid, X, Y);
	if(Y > mid) ret = ret * query(rs(id), mid + 1, r, X, Y);
	return ret;
}
void sol() {
	Init_M();
	build(1, 1, n);
	while(m--) {
		int opt = read(), l = read(), r = read(), ans;
		if(opt == 1) {
			update(1, 1, n, l, r);
		} else {
			Matrix R = query(1, 1, n, l, r);
			ans = (R.a[3][1] + R.a[3][2]) % mod;
			printf("%lld\n", ans);
		}
	}
}
signed main() {
	n = read(), m = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	sol();
	return 0;
}

cpp

本质不同子序列的计数问题

〇#

一#

二#

三#

四#