Submission #222633

#	Time	Username	Problem	Language	Result	Execution time	Memory
222633		kingfran1907	Ljetopica (COI19_ljetopica)	C++14	100 / 100	212 ms	64392 KiB

ljetopica

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 1010;
const llint mod = 1e9+7;

int n, k;
char niz[maxn];
char a[maxn];
char b[maxn];
llint pot[maxn];
char tren[maxn];
llint dp[maxn][maxn][2][2][2];

pair<llint, llint> f(int x, int k, bool rev, bool flag) {
    if (k < 0) return make_pair(0, 0);
    if (x == n) return make_pair(0, (k == 0));

    llint &ret1 = dp[x][k][rev][flag][0];
    llint &ret2 = dp[x][k][rev][flag][1];
    if (ret1 != -1) return make_pair(ret1, ret2);

    pair<int, int> tren;
    ret1 = ret2 = 0;
    if (rev) {
        if (niz[x - 1] == 'R') {
            if (::tren[x] == '0' && flag) tren = f(x + 1, k, true, true);
            else tren = f(x + 1, k, true, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            //printf("lef (%d %d %d %d): %d %d\n", x, k, rev, flag, tren.first, tren.second);

            if (::tren[x] == '0' && flag) tren = make_pair(0, 0);
            else if (::tren[x] == '1' && flag) tren = f(x + 1, k - 1, false, true);
            else if (!flag) tren = f(x + 1, k - 1, false, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            ret1 += tren.second * pot[n - x - 1], ret1 %= mod;
            //printf("rig (%d %d %d %d): %d %d\n", x, k, rev, flag, tren.first, tren.second);
        } else {
            if (::tren[x] == '0' && flag) tren = make_pair(0, 0);
            else if (::tren[x] == '1' && flag) tren = f(x + 1, k, true, true);
            else if (!flag) tren = f(x + 1, k, true, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            ret1 += tren.second * pot[n - x - 1], ret1 %= mod;
            //printf("rig (%d %d %d %d): %d %d\n", x, k, rev, flag, tren.first, tren.second);

            if (::tren[x] == '0' && flag) tren = f(x + 1, k - 1, false, true);
            else tren = f(x + 1, k - 1, false, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            //printf("lef (%d %d %d %d): %d %d\n", x, k, rev, flag, tren.first, tren.second);
        }
    } else {
        if (niz[x - 1] == 'L') {
            if (::tren[x] == '0' && flag) tren = f(x + 1, k, false, true);
            else tren = f(x + 1, k, false, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;

            if (::tren[x] == '0' && flag) tren = make_pair(0, 0);
            else if (::tren[x] == '1' && flag) tren = f(x + 1, k - 1, true, true);
            else if (!flag) tren = f(x + 1, k - 1, true, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            ret1 += tren.second * pot[n - x - 1], ret1 %= mod;
        } else {
            if (::tren[x] == '0' && flag) tren = make_pair(0, 0);
            else if (::tren[x] == '1' && flag) tren = f(x + 1, k, false, true);
            else if (!flag) tren = f(x + 1, k, false, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
            ret1 += tren.second * pot[n - x - 1], ret1 %= mod;

            if (::tren[x] == '0' && flag) tren = f(x + 1, k - 1, true, true);
            else tren = f(x + 1, k - 1, true, false);
            ret1 += tren.first, ret1 %= mod;
            ret2 += tren.second, ret2 %= mod;
        }
    }
    return make_pair(ret1, ret2);
}

int main() {
    scanf("%d%d", &n, &k);
    scanf("%s%s%s", niz, a, b);

    pot[0] = 1;
    for (int i = 1; i < maxn; i++)
        pot[i] = pot[i - 1] * 2, pot[i] %= mod;

    bool flag = false;
    for (int i = 1; i < n; i++)
        if (a[i] == '1') flag = true;

    llint sola = 0;
    if (flag) {
        for (int i = n - 1; i > 0; i--) {
            if (a[i] == '1') {
                a[i] = '0';
                break;
            } else a[i] = '1';
        }

        for (int i = 0; i < n; i++)
            tren[i] = a[i];

        memset(dp, -1, sizeof dp);
        //printf("a: (%lld %lld) (%lld %lld)\n", f(1, k, false, true).first, f(1, k, false, true).second, f(1, k, true, true).first, f(1, k, true, true).second);
        sola = f(1, k, false, true).first + f(1, k, true, true).first + pot[n - 1] * (f(1, k, false, true).second + f(1, k, true, true).second);
        sola %= mod;
    }

    for (int i = 0; i < n; i++)
        tren[i] = b[i];

    memset(dp, -1, sizeof dp);
    //printf("b: (%lld %lld) (%lld %lld)\n", f(1, k, false, true).first, f(1, k, false, true).second, f(1, k, true, true).first, f(1, k, true, true).second);
    llint solb = f(1, k, false, true).first + f(1, k, true, true).first + pot[n - 1] * (f(1, k, false, true).second + f(1, k, true, true).second);
    solb %= mod;

    //printf("debug: %lld %lld\n", sola, solb);
    printf("%lld\n", (solb + mod - sola) % mod);
    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s%s%s", niz, a, b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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