题解

2 条题解

  • 1
    @ 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;
    }
    
    
  • 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%
被复制
4
上传者