2 条题解

• @ 2023-07-11 10:57:56
``````#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;
}

``````
• @ 2020-08-05 19:12:04
``````#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;
}
``````
• 1

ID
2056

5

(无)

(无)

54

21

39%

3