洛谷P5362 [SDOI2019] 连续子序列题解

题目链接：P5362 [SDOI2019] 连续子序列

题意：

我们定义 $\textbf{T. M.}$ 序列$\{T_n\}$为如下形式得布尔序列：
$\begin{aligned} & T_0 = 0 \\[6pt] & T_{2n} = T_n \\[6pt] & T_{2n+1} = 1 - T_n \end{aligned}$
这里我们给出 $\textbf{T. M.}$ 序列的前若干项
$01101001100101101001011001101001\cdots$
$\textbf{T. M.}$ 序列是一个无限长度的序列，它有很多连续子序列。

例如 $0,~1,~10100,~10011$ 和 $011001$ 都是它的连续子序列，然而 $111$ 和 $1000$ 却不是它的连续子序列。

现在给定一个布尔序列（01字符串）$S$ 和一个非负整数 $k$，请统计一下一共有多少种 $\textbf{T. M.}$ 序列的连续子序列 $T$ 满足：

$S$ 是 $T$ 的前缀；

$T$ 是由 $S$ 额外在右侧添加了恰好 $k$ 项形成的。

输入格式

第一行给定一个整数 $T$，表示输入一共含有 $T$ 组数据。

之后$T$行，每一行给定一个 01 字符串 $S$（表示一个布尔序列）和一个非负正整数 $k$，为给定的一组数据。

输出格式

对于每一组数据，输出一行并含有一个整数，表示满足条件的连续子序列个数。

因为数值可能很大，请输出关于 $10^9+9$ 取模后的值。

数据范围：

对于 $100\%$ 的数据，$1\le T\le 100$，给定布尔序列长度不超过 $100$，且 $0\le k\le 10^{18}$ 。

题目的这个序列是 A010060 ，称为 Thue-Morse 序列。

这个序列的构造方式有很多种。

不过~~比较容易发现~~的是：从 $0$ 开始，每次把所有的 $0$ 变成 $01$ ，把所有的 $1$ 变成 $10$ 。

那么对于一个串 S = abcdefg ，我们可以两位一划分，即 ab|cd|ef|g 或 a|bc|de|fg，然后合并每段字符。

如果某一段内两个字符相同，那么这样的划分就是不合法的。

对于两侧落单的段，比如 g 和 a ，显然他们合并前和合并后的结果都是确定的，因此不用特判。

注意到当串的长大于 $3$ 时，合法的切割方案是唯一的，否则会出现 $00$ 或 $11$ 的情况。

那么我们就可以通过对切割方案的计数来实现对串的计数。

设 $f(S,k)$ 表示当前串为 $S$ ，后面接 $k$ 个字符的方案数。

转移只需要把两种情况都试一下，然后记忆化搜索即可，可以用 map 来记状态。

时间复杂度 $\mathcal{O}(T (|S| + \log k))$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define Fi first
#define Se second

typedef pair<string, int> node;

string s; int k; map<node, int> mp;
int solve(const node p)
{
    if(p.Fi.size() == 1) {
        if(!p.Se) return 1; else if(p.Se == 1) return 2; else if(p.Se == 2) return 3;
    }
    if(p.Fi.size() == 2) {
        if(!p.Se) return 1; else if(p.Se == 1) { return p.Fi[0] == p.Fi[1] ? 1 : 2; }
    }
    if(p.Fi.size() == 3 && !p.Se) return !(p.Fi[0] == p.Fi[1] && p.Fi[1] == p.Fi[2]);
    if(mp.count(p)) return mp[p];
    int ans = 0; bool ok = true; string nxt;
    for(int i = 0; i < p.Fi.size(); i += 2)
    {
        if(i == p.Fi.size() - 1) nxt += p.Fi[i];
        else if(p.Fi[i] == p.Fi[i + 1]) { ok = false; break; }
        else nxt += p.Fi[i];
    }
    if(ok) add(ans, solve({nxt, (p.Fi.size() & 1) ? p.Se / 2 : (p.Se + 1) / 2}));
    ok = true; nxt.clear(); (nxt += p.Fi[0] ^ 1);
    for(int i = 1; i < p.Fi.size(); i += 2)
    {
        if(i == p.Fi.size() - 1) nxt += p.Fi[i];
        else if(p.Fi[i] == p.Fi[i + 1]) { ok = false; break; }
        else nxt += p.Fi[i];
    }
    if(ok) add(ans, solve({nxt, (p.Fi.size() & 1) ? (p.Se + 1) / 2 : p.Se / 2}));
    return mp[p] = ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq;
    while(qwq--) { cin >> s >> k; cout << solve({s, k}) % mod << '\n'; }
    return 0;
}