SDOI 2019 连续子序列题解

First Post:

2023-12-20

Last Update:

2023-12-20

果然是我不会的题。现在会了就好。

题面中的序列其实是有名的 Thue-Morse 序列，它有如下三种生成方式：

将序列的前半部分取反后拼在后面
以开始，将序列中每个换成，每个换成。

在本题中，我们要考虑一个串是否在该序列中出现，那从第三种生成方式开始思考是比较适合的。

再考虑的数据范围，这提示我们最终复杂度要么与无关，要么带个。

在生成这个序列时，我们将每个和进行扩大，那么反过来，我们能不能对用类似的过程进行缩小呢？

显然是可以的。我们先以的情况为例，看如何缩小。

我们可以将中的相邻元素每两个分为一组，要求组内不相同，然后保留每组内第一个元素。此过程中头尾可能有落单的段，但是我们可以推理出这些段在原序列中所属的组应该是什么。

容易发现可能的分组方式好像有两种，但我们可以证明，当时，可能的分组方式只有一种。因为如果有两种的话，整个串必然是相间的，那就一定存在一种分组方式使得缩小后出现了或，这显然是不合法的。

也就是说，不断执行上述的缩小过程，并在时特判，我们就能判断一个是否在原序列中出现。

进一步地，一个出现在原序列的，长度的串，与一个合法缩小过程构成了双射。

考虑拓展到原问题，此时我们只需计数合法缩小过程的个数。设原问题答案为，如果就特判，否则把两种分组方式都对用一次，会视情况变为或。然后向合法的情况递归求解即可。注意我们可能不止递归一边，样例中的情况便是一例。

对搜索进行记忆化，用 map 保存二元组的答案。容易发现状态数并不是很多，约为级别，可以通过本题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 9;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
map<pair<string,ll>,int> mp;
inline int Calc(string s,ll k) {
	if(s.size() == 1) {
		if(k <= 2) return k + 1;
	}
	if(s.size() == 2 && k <= 1) {
		if(k == 0) return 1;
		if(k == 1) return s[0] == s[1] ? 1 : 2;
	}
	if(s.size() == 3 && !k) {
		if(s[0] != s[1] || s[1] != s[2]) return 1;
		return 0;
	}
	if(mp.find(make_pair(s,k)) != mp.end())
		return mp[make_pair(s,k)];
	int ans = 0;
	bool OK = 1;
	string nxt;
	// 从第一个开始分
	for(int i = 0;i + 1 < s.size();i += 2) {
		if(s[i] == s[i + 1]) OK = 0;
		nxt += s[i];
	}
	if((s.size()) & 1) nxt += s[(int)s.size() - 1];
	if(OK) Plus(ans,Calc(nxt,(s.size() & 1) ? (k >> 1) : (k + 1 >> 1)));
	OK = 1;
	nxt = s[0] ^ 1;
	for(int i = 1;i + 1 < s.size();i += 2) {
		if(s[i] == s[i + 1]) OK = 0;
		nxt += s[i];
	}
	if(!(s.size() & 1)) nxt += s[(int)s.size() - 1];
	if(OK) Plus(ans,Calc(nxt,(s.size() & 1) ? (k + 1 >> 1) : (k >> 1)));
	return mp[make_pair(s,k)] = ans;
}
int main() {
	int T;
	cin >> T;
	while(T--) {
		string s;ll k;
		cin >> s >> k;
		cout << Calc(s,k) << endl;
	}
	return 0;
}

≡

SDOI 2019 连续子序列 题解

SDOI 2019 连续子序列题解