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

· · 题解

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

一道不错的找规律题

UPDATE on 2020.3.11：修复了炸了的LaTex，修正了几处小笔误使得叙述更加清晰明了

题意简述

定义T.M.序列\{T_n\}为如下形式的01序列：

\begin{cases} T_0=0\\ T_{2n}=T_n\\ T_{2n+1}=1-T_n \end{cases}

给定一个01序列S和一个正整数k，要求统计有多少不同的T.M.序列的连续子序列T满足：

答案对10^9+9取模。

思路详解

根据这个构造方式，我们第一眼能看出的是，每一次在扩大T.M.序列的规模的时候，都是当前的T.M.序列取反后接在右边。比如说0110->01101001。

但是这个构造方式仍然过于复杂，不太好处理。注意到数据范围，k \leq 10^{18}，这个数据范围，不是\Theta(1)就是\Theta(\log_2k)，但是\Theta(1)显然是不太现实的，考虑\Theta(\log_2k)做法，要求我们每次能够把问题规模缩小一半，但是上述的构造方式只对于长度为2^x,x \in N的连续子序列起作用。这个时候我们的目标就转化为了找到一种方法能够将任意连续子序列的规模缩小一半，并且能够还原一开始的子序列。

考虑另外一种构造方式：每一次扩大T.M.子序列，就是往每个0后边加一个1，往每个1后边加一个0。根据这种构造方法不难看出，任意一个合法的连续子序列里边连续的1或者0的个数都\leq 2。考虑找到一个01字符串，它扩大后得到S，那么进行分类讨论：

我们记当前操作得到的字符串是\frac{S}{2}，f(S,k)代表当前01串为S，往后加k位得到的不同的连续子序列个数，则容易得到f(S,k)的递归计算方法。

然后f(S,k)用map存（不然还有啥能存的下啊）。

最后口胡一下，时间复杂度\Theta(T(|S|+\log_2k))

代码时间

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string,ll> var;
int t;
const ll mod=1e9+9; 
string s;
ll k;
map<var,ll> f; 
namespace QiFeng233{
    ll calc(string s,ll k){
        if(s.size()==1){
            if(k==0||k==1||k==2)return k+1;
        }else if(s.size()==2){
            if(k==0)return 1;
            if(k==1)return s[0]==s[1]?1:2;
        }else if(s.size()==3){
            if(k==0)return s[0]!=s[1]||s[1]!=s[2];
        }
        var v=make_pair(s,k);
        if(f.count(v))return f[v];
        string nxt;
        ll ans=0;
        bool successful=true;
        for(int i=0;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?(k>>1):((k+1)>>1)),ans%=mod;
        nxt=s[0]^1;
        successful=true;
        for(int i=1;i<(int)s.size();i+=2){
            if(i<(int)s.size()-1&&s[i]==s[i+1]){
                successful=false;
                break;
            }
            nxt+=s[i];
        }
        if(successful)ans+=calc(nxt,s.size()%2?((k+1)>>1):(k>>1)),ans%=mod;
        return f[v]=ans;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)cin>>s>>k,cout<<QiFeng233::calc(s,k)%mod<<endl;
    return 0;
}

反思总结