Submission #1011079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011079		ksu2009en	Ljetopica (COI19_ljetopica)	C++14	8 / 100	23 ms	31836 KiB

ljetopica

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
 
using namespace std;
typedef long long ll;
 
ll dp[1007][1007][2], pw[10007];
ll sum[1007][1007][2];
ll const mod = (ll)(1e9 + 7);
 
ll get(string &a, string b, ll n, ll k, bool inclusive){
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= k + 1; j++)
            dp[i][j][0] = dp[i][j][1] = 0;
    
    dp[n][0][1] = 1;
    dp[n][1][0] = 1;
    dp[n][0][0] = 1;
    dp[n][1][1] = 1;
    
    if(a[n] == '0'){
        sum[n][0][1] = 1;
        sum[n][1][0] = 1;
    }
    else{
        sum[n][0][0] = 1;
        sum[n][1][1] = 1;
    }
    
    for(int i = n - 1; i >= 1; i--){
        for(int j = 0; j <= k + 1; j++){
            // no add inverse:
                // inverse before:
            char c = (a[i] == '0' ? '1' : '0');
            sum[i][j][1] = (((c == '0' ? 0 : pw[n - i]) * dp[i + 1][j][1]) % mod + sum[i + 1][j][1]) % mod;
            dp[i][j][1] = dp[i + 1][j][1];
            
                // no inverse before
            
            sum[i][j][0] = (((a[i] == '0' ? 0 : pw[n - i]) * dp[i + 1][j][0]) % mod + sum[i + 1][j][0]) % mod;
            dp[i][j][0] = dp[i + 1][j][0];
            
            // add inverse:
            if(j != 0 && i != 1){
                // inverse before = 0 inverse
                sum[i][j][1] = (sum[i][j][1] + (((a[i] == '0' ? 0 : pw[n - i]) * dp[i + 1][j - 1][0]) % mod + sum[i + 1][j - 1][0]) % mod) % mod;
                dp[i][j][1] = (dp[i][j][1] + dp[i + 1][j - 1][0]) % mod;
                
                // no inverse before
                char c = (a[i] == '0' ? '1' : '0');
                sum[i][j][0] = (sum[i][j][0] + (((c == '0' ? 0 : pw[n - i]) * dp[i + 1][j - 1][1]) % mod + sum[i + 1][j - 1][1]) % mod) % mod;
                dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j - 1][1]) % mod;
            }
        }
    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 0; j <= k; j++){
//            cout << i << ' ' << j << ":  " << dp[i][j][0] << ' ' << dp[i][j][1] << endl;
//        }
//        cout << endl << endl;
//    }
//
//    cout << "_____________" << endl;
//
//    for(int i = 1; i <= n; i++){
//        for(int j = 0; j <= k; j++){
//            cout << i << ' ' << j << ":  " << sum[i][j][0] << ' ' << sum[i][j][1] << endl;
//        }
//        cout << endl << endl;
//    }
    
    ll ans = 0, need = 0, last = 0;
    ll cur = pw[n];
    
    for(int i = 1; i <= n; i++){
        // i = first position < b[i]
        
        if(b[i] == '0'){
            if(a[i] != b[i]){
                if(last == 0){
                    need++;
                }
                last = 1;
            }
            else{
                if(last == 1)
                    need++;
                
                last = 0;
            }
            
            continue;
        }
        
        ll need2 = need;
        ll last2 = last;
        
        if(a[i] == '0'){
            if(last == 1){
                need2++;
            }
            last2 = 0;
        }
        else{
            if(last == 0){
                need2++;
            }
            last2 = 1;
        }
        
        ll left0 = k - need2;
        //cout << "     " << i << ' ' << left0 << ' ' << last2 << endl;
        
        if(left0 >= 0){
            bool firstinversion = false;
            if(i == 1){
                if(a[1] == '1')
                    firstinversion = true;
            }
            else{
                if(a[1] != b[1])
                    firstinversion = true;
            }
            
            ll possible = left0 - (firstinversion ? -1 : 1);
            
            ll cnt = 0;
            if(i == n){
                if(left0 == 0 || possible == 0){
                    cnt = cur;
                }
            }
            else{
                cnt = (cur * dp[i + 1][left0][last2]) % mod;
                cnt = (cnt + sum[i + 1][left0][last2]) % mod;
                
                //cout << "!!  " << i << ' ' << left0 << ' ' << dp[i + 1][left0][last2] << ' ' << sum[i + 1][left0][last2] << ' ' << cnt << endl;
                
                if(possible >= 0){
                    ll cnt2 = ((cur * dp[i + 1][possible][last2]) % mod) % mod;
                    cnt2 = (cnt2 + sum[i + 1][possible][last2]) % mod;
                    
                    cnt = (cnt + cnt2) % mod;
                    
                    //cout << "??  " << i << ' ' << possible << ' ' << dp[i + 1][possible][last2] << ' ' << sum[i + 1][possible][last2] << ' ' << cnt2 << endl;
                }
            }
            
            ans = (ans + cnt) % mod;
            //cout << cnt << endl;
        }
        //cout << "last " << last << endl;
        if(a[i] != b[i]){
            if(last == 0){
                need++;
            }
            last = 1;
        }
        else{
            if(last == 1){
                need++;
            }
            last = 0;
 
        }
        
        cur += (b[i] == '0' ? 0 : pw[n - i]);
    }
//    cout << need << ' ' << cur << ' '<< (k - need)<< endl;
    
    if(inclusive){
        if(k - need == 0){
            ans = (ans + cur) % mod;
        }
        else{
            bool firstinversion = false;
            if(a[1] != b[1])
                firstinversion = true;
            
            ll possible = k - need - (firstinversion ? -1 : 1);
            
            if(possible == 0)
                ans = (ans + cur) % mod;
        }
    }
    
    return ans;
}
 
int main(){
    pw[0] = 1;
    
    for(int i = 1; i <= 1001; i++)
        pw[i] = (pw[i - 1] * 2) % mod;
    
    ll n, k;
    cin >> n >> k;
    n--;
    
    string a;
    cin >> a;
    
    for(auto &i: a)
        i = (i == 'L' ? '0' : '1');
    a = '#' + a;
    
    string b, c;
    cin >> b >> c;
    
    auto h2 = get(a, c, n, k, true);


//    cout << h2 << endl;
//
//    return 0;
////
    auto h1 = get(a, b, n, k, false);

    ll ans = (h2 - h1) % mod;
    if(ans < 0)
        ans += mod;
    
    cout << ans << endl;
     
    return 0;
}
/*
 4 0
 RLL
 1011
 1111
 
 */

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