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

题目链接：洛谷

题目大意：询问 Thue-Morse 序列中以 \(S\) 为前缀的长度为 \(k+|S|\) 的字符串个数对 \(10^9+7\) 取模。

你可能需要知道的知识： Thue-Morse 序列的构造方法，一开始序列中只有一个 0，随后对该串进行无限次操作，每次操作将原序列取反后接在原序列之后，所以 Thue-Morse 是一个无穷序列。

题解：这题如果你直接跟着给定的构造方案做的话……请做出来的受我一拜。

考虑换一种构造方案，即对于原序列，每一次在原来的 0 后面增加 1 ，在 1 后面增加 0 ，通过感性理解、举例、归纳可以证明这和原来的构造方案是一样的。

所以说，我们可以对串 \(S\) 进行一些处理，来减小我们的问题的规模。

我们有两种缩小问题规模的方法，一种是将 \(S_{1,2},S_{3,4},\dots\) 缩起来（缩起来的意思是将 01 变为 0 将 10 变为 1，显然如果有连续的 00 或 11 那么就不合法），另一种是将 \(S_{2,3},S_{4,5},\dots\) 缩起来并将 \(S_1\)取反。

所以每一次的操作可以将 \(|S|\) 缩小一半，这样的话直接记忆化搜索就可以做到 \(O(|S|\log k)\) 的时间复杂度。

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int Mod=1000000009;
map,int> f;
int work(string s,ll k){
    if(s.size()==1){
        if(k==0||k==1||k==2){
            return k+1;
        }
    }
    if(s.size()==2){
        if(k==0){
            return 1;
        }
        if(k==1){
            return s[0]==s[1]?1:2;
        }
    }
    if(s.size()==3){
        if(k==0){
            return s[0]!=s[1]||s[1]!=s[2];
        }
    }
    pair u=make_pair(s,k);
    if(f.count(u)>0){
        return f[u];
    }
    int ans=0;
    bool flag=1;
    string v="";
    for(int i=0;i<(int)s.size();i+=2){
        if(i<(int)s.size()-1&&s[i]==s[i+1]){
            flag=0;
            break;
        }
        v+=s[i];
    }
    if(flag){
        ans=(ans+work(v,(s.size()&1)?(k>>1):((k+1)>>1)))%Mod;
    }
    flag=1;
    v=s[0]^1;
    for(int i=1;i<(int)s.size();i+=2){
        if(i<(int)s.size()-1&&s[i]==s[i+1]){
            flag=0;
            break;
        }
        v+=s[i];
    }
    if(flag){
        ans=(ans+work(v,(s.size()&1)?((k+1)>>1):(k>>1)))%Mod;
    }
    return f[u]=ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        string s;
        ll k;
        cin>>s;
        scanf("%lld",&k);
        printf("%d\n",work(s,k));
    }
    return 0;
}
分治洛谷好题

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

洛谷 P2440 木材加工

洛谷 P2404 自然数的拆分问题

洛谷T198835

洛谷 P3817 小A的糖果

洛谷 P1309 瑞士轮 归并排序

洛谷 P2279 [HNOI2003]消防局的设立 贪心

洛谷 P1449 后缀表达式

洛谷 P2791 - 幼儿园篮球题（第二类斯特林数）

洛谷 P3711 - 仓鼠的数学题（多项式）

[洛谷P3345][BZOJ4573][ZJOI2016]大森林（LCT）

题解【洛谷P1046】[NOIP2005] 陶陶摘苹果

标签