oj.uz

Submission #751406

# Submission time Handle Problem Language Result Execution time Memory
751406 2023-05-31T14:10:50 Z Username4132 Ljetopica (COI19_ljetopica) C++14
0 / 100
 18 ms 11260 KB 
#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+=calc(l);
            if(allEq(l, '1')) break;
            nxt(l);
        }
        if(r.back()=='0'){
            ret+=calc(r);
            if(allEq(l, '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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11212 KB Output is correct
2 Correct 9 ms 10580 KB Output is correct
3 Correct 8 ms 10036 KB Output is correct
4 Correct 7 ms 9428 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 9 ms 8400 KB Output is correct
7 Incorrect 8 ms 7580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 11260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11212 KB Output is correct
2 Correct 9 ms 10580 KB Output is correct
3 Correct 8 ms 10036 KB Output is correct
4 Correct 7 ms 9428 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 9 ms 8400 KB Output is correct
7 Incorrect 8 ms 7580 KB Output isn't correct
8 Halted 0 ms 0 KB -