Submission #707940

#	Time	Username	Problem	Language	Result	Execution time	Memory
707940		AnasAAF	Ljetopica (COI19_ljetopica)	C++17	0 / 100	1 ms	212 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define float double

int n, k;
string stp;
ll sum(0);
ll MOD = 1000000007;
ll mini, maxi;

ll toDecimal(string s){
    ll ans(0), num(1);
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]=='1')ans+=num;
        num=num<<1;
    }
    return ans;

}

void dfs(ll node, ll ind, bool rev){
    if(ind>=(ll)stp.size()){
         if(node>=mini && node<=maxi){sum = ((sum%MOD)+(node%MOD))%MOD;}
         //cout<<node<<endl;
         return;
    }
    if(stp[ind]=='R'){
        if(rev){
            dfs((node*2)%MOD, ind+1, rev);
        }
        else{
            dfs(((node*2)+1)%MOD, ind+1, rev);
        }
    }
    else{
        if(rev){
            dfs(((node*2)+1)%MOD, ind+1, rev);
        }
        else{
            dfs(((node*2))%MOD, ind+1, rev);
        }
    }
    return;
}

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    cin>>stp;
    string left, right;cin>>left>>right;
    mini = toDecimal(left);maxi=toDecimal(right);
    dfs(1, 0, 0);
    dfs(1, 0, 1);
    cout<<sum<<endl;

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 17
• Subtask 4: 0 / 61