题目链接：洛谷
题目大意：询问 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 <map>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int Mod=1000000009;
map<pair<string,ll>,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<string,ll> 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
",work(s,k));
}
return 0;
}