Submission #1108455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108455		juliany2	Ljetopica (COI19_ljetopica)	C++17	100 / 100	87 ms	64080 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;

const int N = 1007;
int n, m;
string s, l, r;
ll p2[N];
// [idx][flips][last][restricted]
ll cnt[N][N][2][2], sum[N][N][2][2];

ll solve(string x) {
    memset(cnt, 0, sizeof(cnt));
    memset(sum, 0, sizeof(sum));

    cnt[0][0][0][1] = cnt[0][0][1][1] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k : {0, 1}) {
                int p = s[i] == '1';
                int q = p ^ 1;

                if (x[i] == '0') {
                    (cnt[i][j + (k != q)][q][1] += cnt[i - 1][j][k][1]) %= mod;
                    (sum[i][j + (k != q)][q][1] += sum[i - 1][j][k][1]) %= mod;
                }
                else {
                    (cnt[i][j + (k != p)][p][1] += cnt[i - 1][j][k][1]) %= mod;
                    (sum[i][j + (k != p)][p][1] += sum[i - 1][j][k][1]) %= mod;
                    (sum[i][j + (k != p)][p][1] += cnt[i - 1][j][k][1] * p2[i] % mod) %= mod;

                    (cnt[i][j + (k != q)][q][0] += cnt[i - 1][j][k][1]) %= mod;
                    (sum[i][j + (k != q)][q][0] += sum[i - 1][j][k][1]) %= mod;
                }

                (cnt[i][j + (k != p)][p][0] += cnt[i - 1][j][k][0]) %= mod;
                (sum[i][j + (k != p)][p][0] += sum[i - 1][j][k][0]) %= mod;
                (sum[i][j + (k != p)][p][0] += cnt[i - 1][j][k][0] * p2[i] % mod) %= mod;

                (cnt[i][j + (k != q)][q][0] += cnt[i - 1][j][k][0]) %= mod;
                (sum[i][j + (k != q)][q][0] += sum[i - 1][j][k][0]) %= mod;
            }
        }
    }

    ll res = 0;
    for (int j : {0, 1}) {
        for (int k : {0, 1}) {
            (res += sum[n - 1][m][j][k]) %= mod;
            (res += cnt[n - 1][m][j][k] * p2[0] % mod) %= mod;
        }
    }

    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> s >> l >> r;

    for (char &c : s) {
        c = (c == 'L' ? '0' : '1');
    }
    s = '1' + s;

    p2[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--)
        p2[i] = p2[i + 1] * 2 % mod;

    ll ans = (solve(r) - solve(l) + mod) % mod;

    int cnt = 0;
    int lst = l[1] == s[1];
    for (int i = 2; i < n; i++) {
        int here = l[i] == s[i];
        if (here != lst)
            cnt++;
        lst = here;
    }

    if (cnt == m - 1 || cnt == m) {
        for (int i = 0; i < n; i++) {
            if (l[i] == '1')
                (ans += p2[i]) %= mod;
        }
    }

    cout << ans << '\n';

    return 0;
}

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