ARC110E Shorten ABC

ARC110E Shorten ABC

考虑操作的本质，将 $A$、$B$、$C$ 分别记作 $1$、$2$、$3$。

操作 $s_i$ 和 $s_{i+1}$ 即合并为 $s_i\oplus s_{i+1}$。

那么区间的异或和并不变，对于异或和为 $0$ 的区间，最后只会全部相同；否则一定剩下一个字符（奇数且全部相同的除外）。

推论，对于异或和为 $0$ 的区间，若在它左或右边多加上一个字符，一定会合并成一个字符。

对于一种操作得到的字符串 $t$，相等于将原串前面全部分成异或和不为 $0$ 的段，且满足最后一段异或和为 $0$（空串也算）。

普通 DP 具备重复性，重复是因为异或和为 $0$ 的段可能有多种可能方案。

于是考虑去除异或和为 $0$ 的段的贡献即不枚举其，考虑当前段结尾为 $i$，找到它右边第一个 $j$，满足区间 $[1,j]$ 的前缀异或和 $\ne$ 区间 $[1,i]$ 的异或和，即表示区间 $[i+1,j]$ 的异或和不为 $0$。

记 $f_i$ 表示按上述方法分段，最后一段以 $i$ 结尾的方案数。

预处理上述方法的递推顺序即可。

答案即为满足 $[i+1,n]$ 的异或和为 $0$ 的所有 $i$ 对应的 $f_i$ 之和。

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

类似的练手题：AT4379 [AGC027E] ABBreviate。

#include

using namespace std;

typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
	int 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 << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 1e6 + 10, mod = 1e9 + 7;

int n, s[_], nxt[_][4], f[_];

char c[_];

signed main() {
	n = read();
	scanf("%s", c + 1);
	bool flg = 0;
	for (int i = 1; i < n; ++i)
		if (c[i] != c[i + 1]) {
			flg = 1;
			break;
		}
	if (!flg) return puts("1"), 0;
	for (int i = 1; i <= n; ++i) s[i] = s[i - 1] ^ (c[i] - 'A' + 1);
	for(int i = 0; i < 4; ++i) nxt[n][i] = n + 1;
	for (int i = n; i >= 1; --i) {
		for (int j = 0; j < 4; ++j) nxt[i - 1][j] = nxt[i][j];
		nxt[i - 1][s[i]] = i;
	}
	f[0] = 1;
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j)
			if(s[i] != j) f[nxt[i][j]] = (f[nxt[i][j]] + f[i]) % mod;
		if(s[i + 1] == s[n]) ans = (ans + f[i + 1]) % mod;
//		cout << f[i + 1] << "\n";
	}
	write(ans), he;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65