自动搬运

查看原文

来自洛谷，原作者为

	QiFeng233 如果你比别人老还比别人菜，就得加倍努力

搬运于2025-08-24 22:09:59，当前版本为作者最后更新于2020-03-10 23:46:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题解】[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$满足：

• $S$是$T$的前缀
• $T$是$S$在右侧恰好添加了$k$项形成的。

答案对$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$，那么进行分类讨论：

• $|S|$为偶数，那么有两种方案：

  • 把S每两位字符分为一组，然后01->0，10->1。注意如果某一组是11或者00，那这种方式行不通。
  • 把S从$S_2$到$S_{|S|-1}$每两位字符分为一组，然后01->0，10->1。注意如果某一组是11或者00，那这种方式行不通。

  可以证明，对于$\forall S$，若有解，则有且仅有一种方式有解。注意$|S|=2$时仅能用方案一。

• $|S|$为奇数，那么有两种方案：

  • 把S从$S_1$到$S_{|S|-1}$每两位字符分为一组，然后01->0，10->1。注意如果某一组是11或者00，那这种方式行不通。
  • 把S从$S_2$到$S_{|S|}$每两位字符分为一组，然后01->0，10->1。注意如果某一组是11或者00，那这种方式行不通。注意在这种方式下，找到的字符串第一位是$S_1xor1$。

  可以证明，对于$|S|>3$，若有解，则有且仅有一种方式有解。

我们记当前操作得到的字符串是$\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;
}

反思总结

• 思维题往往不需要多少算法知识，这题就只用了基础算法——分治。
• 思维题要求能跳出思维定势，灵活思考。就像这题，如果不能想到上文提到的构造方式而只是照着题目给你的构造方式死刚，是不会有结果的。
• 面向数据编程，就像看到$k \leq 10^{18}$就能想到$\Theta(1)$或者$\Theta(\log_2k)$从而想出正解。
• 这个$T.M.$序列全名Thue−Morse序列。仔细一想，好像我以前见过它几次，但是我没一次做出来了/kk
• 这题模数是$10^9+9$，但我一开始模了$10^9+7$/kk