「SDOI2019」连续子序列

发表于 | 更新于 | 分类于 | 阅读次数：

一道神仙题，场上只想到一半不到……

[LOJ 3115]

[Luogu 5362]

题意简述

$\text{Thue−Morse}$ 序列是一个无限长度的序列 $\left\langle T_n\right\rangle$ ：

  • $T_0 = 0$ ；
  • $T_{2n} = T_n$ ；
  • $T_{2n + 1} = 1 - T_n$ 。( $n > 0$ )

显然这是一个 $\text{01}$ 序列。现在给定一个 $01$ 序列 $S$ 和一个非负整数 $k$ ，求 $\text{Thue-Morse}$ 序列中有多少本质不同的连续子序列 $T$ 满足：

  • $S$ 是 $T$ 前缀；
  • $|T| = |S| + k$ ，其中 $|x|$ 表示 $\text{02}$ 序列 $x$ 的长度。

数据组数 $case \le 100$ ， $|S| \le 100$ ， $0\le k\le 10^{18}$ ，答案模 $10^9+9$ 。

主要思路

据说 $\text{Thue-Morse}$ 序列被出到过很多找规律题里？然而本人才第一次见，充分说明本人刷题量还大大不足……

由于这个序列是个 $\text{01}$ 序列，所以下文可能会把这个序列当成一个 $\text{01}$ 字符串。

关于 $\text{Thue-Morse}$ 序列的性质

以下简称 $\text{Thue-Morse}$ 为 $\text{T.M.}$ 。

场上通过手玩样例和瞪这个序列，不难发现几个性质：

  1. 每次这个序列会将上一次生成的子串中， 1 变为 10 ， 0 变为 01 ，接入总串尾部，这我们称为一次生成。
    例如，一开始的串是 01 ，上一次生成的串是 1 。接着，这个串会以此变成 0110 , 01101001 , 0110100110010110 ……
  2. 除了 000 与 111 之外，其他长度不大于 $3$ 的 $\text{01}$ 字符串都是 $\text{T.M.}$ 串的子串。
    同时，如果一个串 $s$ 中有至少三个 1 或 0 相连，那么这个串不可能是 $\text{T.M.}$ 的子串。
  3. 对于一个长度大于 $3$ 的串 $s$ ，如果其是 $\text{T.M.}$ 串的子串，它必然是由一长度为 $\lceil\dfrac{n}{2}\rceil$ 或 $\lceil\dfrac{n + 1}{2}\rceil$ 的 $\text{T.M.}$ 串的子串 $t$ 生成的。发现并不用考虑 $t$ 是不是一次生成了 $s$ ，因为即使 $t$ 并不是一次就生成了 $s$ ，生成的 $s$ 也会是连续的。

对于上面的第三条，考虑如何通过 $s$ 反推回 $t$ 。大概思路就是将 01 写为 0 ，将 10 写为 1 ，适当在串前后补字符。

看几个例子：
  1. 011001 是如何生成的？
    显然这个串可以通过 010 生成。
  2. 001100 是如何生成的？
    考虑 1010 可以生成 10011001 ，可得 001100 也是由 1010 生成的。
  3. 10010 是如何生成的？
    和上面的串思路差不多，发现是由 100 生成的。
  4. 10110 是如何生成的？
    也和上面的串思路差不多，发现是由 001 生成的。
  5. 0011001100 是如何生成的？
    沿着刚刚的思路推，发现是由 101010 生成的。而 101010 是由 111 生成的。由于 111 不是 $\text{T.M.}$ 串的子串，所以 0011001100 不是 $\text{T.M.}$ 串的子串。

通过上面的几个例子，又可以大致看出一个结论：
  1. 对于一个长度大于 $3$ 的串 $s$ ，如果其是 $\text{T.M.}$ 串的子串，它必然是由且仅可能由一长度为 $\lceil\dfrac{n}{2}\rceil$ 或 $\lceil\dfrac{n + 1}{2}\rceil$ 的 $\text{T.M.}$ 串的子串 $t$ 生成的。即不可能通过两个不同的串生成出相同的串。
如何证明？

如果串 $s$ 有子串 00 或子串 11 ，因为 0 和 1 生成一次产生的串不能是 00 或 11 ，若 $s$ 是 $\text{T.M.}$ 串的子串则 $s$ 只有一种生成方式。

如果串 $s$ 无子串 00 或子串 11 ：

  • 若长度大于 $4$ ，则可以由 0...0 （或 1...1） 生成，但由于长度大于 $4$ ，所以 0 （或 1） 的数量不小于 $3$ ，该串不在 $\text{T.M.}$ 串中。
  • 若长度等于 $4$ ，则 0101 由 00 、 1010 由 11 构成。

所以我们终于得出了这题最重要的一个结论。

利用该结论 dp

考虑 $dp(k)$ 为，一个长为 $1$ 的 $\text{01}$ 字符串后任意插入一个长为 $k$ 的后缀，这个串是 $\text{T.M.}$ 的子串的总数。

发现这个串 $1$ 开始是 0 或是 1 答案是相同的。下文钦定这个长为 $1$ 的字符串从 0 开始。

由于这个串一定是由唯一的 $t$ 串生成的，考虑像上文一般寻找这个 $t$ 串。

如果不在串前补 1 ，则 $t$ 串是从 0 开始的一个串，后接了长度是 $\lceil\dfrac{k - 1}{2}\rceil$ 的任意后缀，即有 $dp(\lceil\dfrac{k - 1}{2}\rceil)$ 种串在 $\text{T.M.}$ 串内；如果在串前补 1 ，则 $t$ 串是从 1 开始的一个串，同理可得有 $dp(\lceil\dfrac{k}{2}\rceil)$ 种 $t$ 串。故得到 $dp(k) = dp(\lceil\dfrac{k - 1}{2}\rceil) + dp(\lceil\dfrac{k}{2}\rceil)$ 。

考虑边界状态。显然，若 $k<3$ 可以预处理出来。$dp(0) = 1, dp(1) = 2, dp(2) = 3$ 。（由于不能是 000 所以 $dp(2) = 3$ ）

最后推得答案

设 $Calc(S,k)$ 是询问串为 $S$ ，后缀长度为 $k$ 的答案。

类似 $|S| = 1$ 的询问，可以先确定 $S$ 串是由什么串生成而来的。同样类似 $|S| = 1$ 的询问讨论 $k$ 的取值，注意细节即可。

复杂度没仔细分析……大概一个询问是 $O(|S| + \log_2k)$ 左右？

参考代码

其实代码挺短的，但是为啥把同步关了之后在洛谷 MLE ，在 LOJ RE ……

然而即使没关同步也跑得飞快。
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline LL read(){
        reg LL ans=0,f=1;reg char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=ans*10+c-'0'; return f?ans:-ans;
    }
    Templ(_Tp) inline void write(_Tp x){
        if(x < 0) return (void)(putchar('-'), write(-x));
        if(x < 10) return void(putchar( int(x) ^ 48 ));
        return (void)(write(x / 10), putchar( int(x % 10) ^ 48 ));
    }
    Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
    Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
    #define using_mod
    const int mod = 1000000009;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

#define rsiz(x) (int)(x.size())
map<LL, int> dp;
inline int moded_add(int a, int b){ return (a += b) >= mod ? a -= mod : a; }

int Function(LL k){
    if(dp[k]) return dp[k];
    if(k < 3) return k + 1;
    return (dp[k] = moded_add(Function(k >> 1), Function((k + 1) >> 1)));
}

inline int Generate(const string &S, string &T){//判断 S 串是否能被生成并反推得可生成 S 串的 T 串
    T.clear();
    for(Rint i = 0, ed_i = rsiz(S); i < ed_i; i += 2){
        if(i + 1 == ed_i) T += (S[i] == '0') ? "0" : "1";
        else{
            if(int(S[i]) ^ int(S[i + 1])) T += (S[i] == '0') ? "0" : "1";
            else return 0;
        }
    }
    return 1;
}

int Calc(const string &S, const LL &k){
    Rint siz = rsiz(S);
    if(siz == 1) return Function(k);
    if(siz == 2 && k < 2) return k == 1 ? (S[0] == S[1] ? 1 : 2) : 1;
    if(siz == 3 && k == 0) return S[0] != S[1] || S[1] != S[2];
    string T;
    Rint res = 0;
    if(Generate(S, T)){
        inc(res, Calc(T, (k + (!(siz & 1))) >> 1));
    }
    if(Generate((S[0] == '0' ? "1" : "0") + S, T)){
        inc(res, Calc(T, (k + (siz & 1)) >> 1));
    }//缩串，注意处理后缀串长度
    return res;
}

inline void sdoi_work(){
    string S;
    LL k;
    cin >> S >> k;
    write(Calc(S, k)), putchar('\n');
}

int main(){
// 	ios::sync_with_stdio(false);
    Rint sdoi_2019_score = read();
    while(sdoi_2019_score --) sdoi_work();
    return 0;
}

参考资料

zxyoi_dreamer 的 blog