oj.uz

답안 #1009669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009669 2024-06-27T19:23:20 Z ksu2009en Ljetopica (COI19_ljetopica) C++14
22 / 100
 25 ms 29532 KB 
#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; i++)
        for(int j = 0; j <= n; 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; 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 = -1;
    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){
            ll cnt = 0;
            if(i == n){
                if(b[i] == '1'){
                    if(left0 <= 1)
                        cnt = cur;
                }
            }
            else{
                cnt = (cur * dp[i + 1][left0][last2]) % mod;
                cnt = (cnt + sum[i + 1][left0][last2]) % mod;
                
               // cout << "!!  " << dp[i + 1][left0][last2] << ' ' << sum[i + 1][left0][last2] << endl;
                
                if(left0 != 0){
                    cnt = (cnt + (cur * dp[i + 1][left0 - 1][last2]) % mod) % mod;
                    cnt = (cnt + sum[i + 1][left0 - 1][last2]) % mod;
                    
                    //cout << "??  " << dp[i + 1][left0 - 1][last2] << ' ' << sum[i + 1][left0 - 1][last2] << 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(need <= k && k - need <= 1 && inclusive){
        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 h1 = get(a, b, n, k, false);

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

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22616 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20312 KB Output is correct
4 Correct 3 ms 20060 KB Output is correct
5 Correct 3 ms 21460 KB Output is correct
6 Correct 2 ms 19292 KB Output is correct
7 Correct 3 ms 19292 KB Output is correct
8 Correct 2 ms 19804 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4536 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 29532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22616 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20312 KB Output is correct
4 Correct 3 ms 20060 KB Output is correct
5 Correct 3 ms 21460 KB Output is correct
6 Correct 2 ms 19292 KB Output is correct
7 Correct 3 ms 19292 KB Output is correct
8 Correct 2 ms 19804 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4536 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Incorrect 25 ms 29532 KB Output isn't correct
25 Halted 0 ms 0 KB -