题解 P5362 【[SDOI2019]连续子序列】

· · 题解

题目大意：有一个01串tm，满足tm(0)=0，tm(i)=tm(i>>1)^(i&1)。给定01串s和整数k，问有多少个本质不同的01串t满足：t是tm的子串，s是t的前缀，t的长度是|s|+k。

全场无人ac的找规律神题。

关于tm序列，有很多种解释方式，比如每个数的二进制中1的个数的奇偶性啦，从0开始每次把自身取反接在后面啦等等。对于这个题，最好的解释方式是这样的：

从0开始，每次把所有的0变成01，把所有的1变成10。

为什么这样解释最好呢？因为我们可以试着把一个tm的子串用这种方式变换回去：

假设一个串s=abcdefg

我们可以把它每2位划分为一段，即ab|cd|ef|g或a|bc|de|fg，然后把每一段按上述规则合并为一个字符。

如果某一段内两个字符相同，意味着这样划分是不合法的。

两侧也许有落单的段，但是根据规则实际上与它们成一段的另一个字符是确定的，我们也可以将其补上。

比如串10100110010，就可以切割为10|10|01|10|01|0，然后合并成110100。

可以验证：当串长>3时，合法的切割方案是唯一的。比如串1001，就只能划分为10|01,而串1010看似可以划分为1|01|0，但是由于这样缩成的是000因此不合法，所以唯一的划分方案是10|10。

因此我们就可以通过对切割方案的计数来实现对串的计数。设f(s,k)表示当前串为s，后面接k个字符的方案数。当|s|+k<=3时特判，否则枚举2种划分方案，对于合法的方案进行递归操作。用个map对状态进行记忆化即可。

本质不同的状态数大约只有O(|s|+logk)级别，可以通过此题。

#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
int t;
string s;
li k;
#define psi pair<string,li>
#define fi first
#define se second
#define mp make_pair
map<psi,li> mm;
const int mo = 1000000009;
inline li wk(psi p){
    if(p.fi.size() == 1){
        if(!p.se) return 1;
        if(p.se == 1) return 2; 
        if(p.se == 2) return 3;
    }
    if(p.fi.size() == 2){
        if(!p.se) return 1;
        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] ? 0 : 1);
    if(mm.find(p) != mm.end()) return mm[p];
    li as = 0;
    int i;
    bool fg = 1;
    string nxt;
    nxt.clear();
    for(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]){
            fg = 0;break;
        }
        else nxt += p.fi[i];
    } 
    if(fg) as += wk(mp(nxt,(p.fi.size() % 2 ? (p.se >> 1) : (p.se + 1 >> 1))));
    fg = 1;nxt.clear();
    nxt += (p.fi[0] ^ 1);
    for(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]){
            fg = 0;break;
        }
        else nxt += p.fi[i];
    } 
    if(fg) as += wk(mp(nxt,(p.fi.size() % 2 ? (p.se + 1 >> 1) : (p.se >> 1))));
    return mm[p] = as;
}
int main(){
    cin>>t;
    while(t--){
        cin>>s>>k;
        cout<<wk(mp(s,k)) % mo<<endl;
    }
    return 0;
}