题解：P12087 [RMI 2019] 好数 / Lucky Numbers

还算较为简单的一道数据结构吧。

首先，我们考虑这样的一个问题：给定一个数，求所有小于等于它的数中不包含 13 子段的有多少个。我们可以使用数位 DP 解决：设计状态 dp_i, j, k 表示考虑了前 i 个数位，是否全部等于最高值，上一个是否为 1。这个的转移式是很好写的，直接大力分讨一下即可。

对于第 i 位，原数字该位为 d_i，当前选择的数字为 x：

dp_{i + 1, j^′, k^′}+ = dp_i, j, k

其中：

• 边界条件：
  • 如果 j = 1：x ∈ [0, d_i]
  • 如果 j = 0：x ∈ [0, 9]
  • 如果 k = 1 且 x = 3，则为不合法状态，跳过。
• 目标状态：
  • $j' = \begin{cases} 1 & \text{if } j = 1 \text{ and } x = d_i \\ 0 & \text{otherwise} \end{cases}$
  • $k' = \begin{cases} 1 & \text{if } x = 1 \\ 0 & \text{otherwise} \end{cases}$

答案就是 $\displaystyle\sum_{j=0}^{1} \sum_{k=0}^{1} dp_{n,j,k}$。

不难发现这个式子可以直接进行区间合并的，然后放到线段树上这道题就做完了。

具体而言，我们定义每个区间拥有一个计数 cnt_{i, j, k, l}，表示当前区间从状态 i, j 转移到 k, l 有多少种情况，转移是简单的，具体请看代码。

代码：

#include<bits/stdc++.h>
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
using namespace std;
const int mod = 1000000007;
int n, X[100000 + 5];
struct Seg_Tree {
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
#define mid (l + r >> 1)
#define lson lc(p), l, mid
#define rson rc(p), mid + 1, r
	struct Node {
		int cnt[2][2][2][2];
		Node() {
			memset(cnt, 0, sizeof(cnt));
		}
		friend Node operator+(const Node& a, const Node& b) {
			Node c;
			for (bool t0 : {0, 1})
				for (bool s0 : {0, 1})
					for (bool t1 : {0, 1})
						for (bool s1 : {0, 1})
							for (bool t2 : {0, 1})
								for (bool s2 : {0, 1})
									c.cnt[t0][s0][t2][s2] = (c.cnt[t0][s0][t2][s2] + 1ll * a.cnt[t0][s0][t1][s1] * b.cnt[t1][s1][t2][s2] % mod) % mod;
			return c;
		}
		Node(int d) {
			memset(cnt, 0, sizeof cnt);
			for (bool t0 : {0, 1})
				for (bool s0 : {0, 1})
					for (int i = 0, lim = (t0 ? d : 9); i <= lim; ++i) {
						if (s0 == 1 && i == 3) continue;
						cnt[t0][s0][t0 && i == d][i == 1] = (cnt[t0][s0][t0 && i == d][i == 1] + 1) % mod;
					}
		}
	}tree[100000 << 2 | 3];
	void pushup(int p) {
		tree[p] = tree[lc(p)] + tree[rc(p)];
	}
	void build(int p, int l, int r) {
		if (l == r) {
			tree[p] = X[l];
			return;
		}
		build(lson); build(rson);
		pushup(p);
	}
	void update(int p, int l, int r, int x, int k) {
		if (l == r) {
			tree[p] = X[l] = k;
			return;
		}
		if (x <= mid) update(lson, x, k);
		else update(rson, x, k);
		pushup(p);
	}
	Node query(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return tree[p];
		if (x <= mid && mid < y) return query(lson, x, y) + query(rson, x, y);
		if (x <= mid) return query(lson, x, y);
		if (mid < y) return query(rson, x, y);
	}
}t;
int main() {
	// file(number);
	cin.tie(0)->sync_with_stdio(false);
	int Q; string s; cin >> n >> Q >> s;
	for (int i = 0; i < n; i++) X[i] = s[i] - '0';
	t.build(1, 0, n - 1);
	auto root = t.query(1, 0, n - 1, 0, n - 1);
	int ans = 0;
	for (bool t1 : {0, 1})
		for (bool s1 : {0, 1})
			ans = (ans + root.cnt[1][0][t1][s1]) % mod;
	cout << ans << endl;
	for (int i = 0; i < Q; i++) {
		int opt;  cin >> opt;
		if (opt == 1) {
			int L, R; cin >> L >> R;
			auto node = t.query(1, 0, n - 1, L - 1, R - 1);
			int res = 0;
			for (bool t1 : {0, 1})
				for (bool s1 : {0, 1})
					res = (res + node.cnt[1][0][t1][s1]) % mod;
			cout << res << endl;
		}
		else if (opt == 2) {
			int a, b; cin >> a >> b;
			t.update(1, 0, n - 1, a - 1, b);
		}
	}
	return 0;
}