洛谷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;
}