Submission #751423

#	Time	Username	Problem	Language	Result	Execution time	Memory
751423		Username4132	Ljetopica (COI19_ljetopica)	C++14	100 / 100	18 ms	11340 KiB

ljetopica

#include<iostream>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)

const int MAXN=1010, MOD=1000000007;
int n, k, pot[MAXN], comb[MAXN][MAXN], dp[MAXN][MAXN][2];
string dirs, le, ri;

void pre(string& num){
    int pos=num.size()-1;
    while(num[pos]=='0') num[pos--]='1';
    num[pos]='0';
}

void nxt(string& num){
    int pos=num.size()-1;
    while(pos>0 && num[pos]=='1') num[pos--]='0';
    num[pos]='1';
}

bool allEq(string& num, char ch){
    bool ret=true;
    for(char c:num) ret&=(c==ch);
    return ret;
}

int calc(string num){
    int ret=0;
    forn(dir, 2){
        int xtra=0, sum=0;
        bool cur=dir;
        forsn(i, 1, num.size()){
            bool differs=cur^(num[i]=='0')^(dirs[i-1]=='L');
            xtra+=(int)differs;
            cur^=differs;
        }
        forn(i, num.size()) if(num[i]=='1') sum=(sum + pot[n-1-i])%MOD;
        if(xtra<=k) ret=(ret+dp[n-num.size()][k+1-xtra][cur]+((ll)comb[n-num.size()][k+1-xtra])*sum)%MOD;
    }
    return ret;
}

int query(string l, string r){
    int ret=0;
    for(; l<=r; l.pop_back(), r.pop_back()){
        if(l.back()=='1'){
            ret=(ret+calc(l))%MOD;
            if(allEq(l, '1')) break;
            nxt(l);
        }
        if(r.back()=='0'){
            ret=(ret+calc(r))%MOD;
            if(allEq(r, '0')) break;
            pre(r);
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> dirs >> le >> ri;
    pot[0]=1;
    forn(i, n) pot[i+1]=(pot[i]<<1)%MOD;
    forn(i, n+1) comb[i][1]=comb[i][i+1]=1;
    forsn(i, 2, n+1) forsn(j, 1, n) comb[i][j+1]=(comb[i-1][j+1]+comb[i-1][j])%MOD;
    forsn(i, 1, n) forsn(j, 1, i+2) forn(d, 2){
        dp[i][j][d]=(dp[i-1][j][d] + dp[i-1][j-1][d^1] + comb[i-1][j-(d^(dirs[n-i-1]=='L'))]*((ll)pot[i-1]))%MOD;
    }
    cout << query(le, ri) << "\n";
}

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