Submission #144139

#	Time	Username	Problem	Language	Result	Execution time	Memory
144139		SamAnd	Ljetopica (COI19_ljetopica)	C++17	100 / 100	145 ms	63528 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
const long long M = 1000000007;

int n, k;
char a[N];
char ll[N], rr[N];

long long dp[N][N][2][2];
long long dpq[N][N][2][2];

char t[N];
long long solv()
{
    memset(dp, 0, sizeof dp);
    memset(dpq, 0, sizeof dpq);
    dp[0][0][0][1] = 1;
    dpq[0][0][0][1] = 1;
    dp[0][0][1][1] = 1;
    dpq[0][0][1][1] = 1;
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            for (int z = 0; z < 2; ++z)
            {
                if ((z == 0 && a[i] == 'L') || (z == 1 && a[i] == 'R'))
                {
                    // 1
                    if (t[i + 1] == '0')
                    {
                        dp[i + 1][j][z][1] = (dp[i][j][z][1] * 2 + dp[i + 1][j][z][1]) % M;
                        dpq[i + 1][j][z][1] = (dpq[i][j][z][1] + dpq[i + 1][j][z][1]) % M;
                    }
                    else
                    {
                        dp[i + 1][j][z][0] = (dp[i][j][z][1] * 2 + dp[i + 1][j][z][0]) % M;
                        dpq[i + 1][j][z][0] = (dpq[i][j][z][1] + dpq[i + 1][j][z][0]) % M;
                        dp[i + 1][j + 1][z ^ 1][1] = (dp[i][j][z][1] * 2 + dpq[i][j][z][1] + dp[i + 1][j + 1][z ^ 1][1]) % M;
                        dpq[i + 1][j + 1][z ^ 1][1] = (dpq[i][j][z][1] + dpq[i + 1][j + 1][z ^ 1][1]) % M;
                    }
                    // 0
                    dp[i + 1][j][z][0] = (dp[i][j][z][0] * 2 + dp[i + 1][j][z][0]) % M;
                    dpq[i + 1][j][z][0] = (dpq[i][j][z][0] + dpq[i + 1][j][z][0]) % M;
                    dp[i + 1][j + 1][z ^ 1][0] = (dp[i][j][z][0] * 2 + dpq[i][j][z][0] + dp[i + 1][j + 1][z ^ 1][0]) % M;
                    dpq[i + 1][j + 1][z ^ 1][0] = (dpq[i][j][z][0] + dpq[i + 1][j + 1][z ^ 1][0]) % M;
                }
                else
                {
                    // 1
                    if (t[i + 1] == '0')
                    {
                        dp[i + 1][j + 1][z ^ 1][1] = (dp[i][j][z][1] * 2 + dp[i + 1][j + 1][z ^ 1][1]) % M;
                        dpq[i + 1][j + 1][z ^ 1][1] = (dpq[i][j][z][1] + dpq[i + 1][j + 1][z ^ 1][1]) % M;
                    }
                    else
                    {
                        dp[i + 1][j + 1][z ^ 1][0] = (dp[i][j][z][1] * 2 + dp[i + 1][j + 1][z ^ 1][0]) % M;
                        dpq[i + 1][j + 1][z ^ 1][0] = (dpq[i][j][z][1] + dpq[i + 1][j + 1][z ^ 1][0]) % M;
                        dp[i + 1][j][z][1] = (dp[i][j][z][1] * 2 + dpq[i][j][z][1] + dp[i + 1][j][z][1]) % M;
                        dpq[i + 1][j][z][1] = (dpq[i][j][z][1] + dpq[i + 1][j][z][1]) % M;
                    }
                    // 0
                    dp[i + 1][j + 1][z ^ 1][0] = (dp[i][j][z][0] * 2 + dp[i + 1][j + 1][z ^ 1][0]) % M;
                    dpq[i + 1][j + 1][z ^ 1][0] = (dpq[i][j][z][0] + dpq[i + 1][j + 1][z ^ 1][0]) % M;
                    dp[i + 1][j][z][0] = (dp[i][j][z][0] * 2 + dpq[i][j][z][0] + dp[i + 1][j][z][0]) % M;
                    dpq[i + 1][j][z][0] = (dpq[i][j][z][0] + dpq[i + 1][j][z][0]) % M;
                }
            }
        }
    }
    long long ans = 0;
    for (int z = 0; z < 2; ++z)
    {
        for (int g = 0; g < 2; ++g)
        {
            ans = (ans + dp[n - 1][k][z][g]) % M;
        }
    }
    return ans;
}

long long stg()
{
    long long ans = 1;
    for (int i = 1; i < n; ++i)
    {
        if (t[i] == '0')
            ans = (ans * 2) % M;
        else
            ans = (ans * 2 + 1) % M;
    }
    int kk = k;
    bool z = false;
    for (int i = 1; i < n; ++i)
    {
        if ((z == false && a[i - 1] == 'L') || (z == true && a[i - 1] == 'R'))
        {
            if (t[i] == '0')
                continue;
            else
            {
                z ^= true;
                --kk;
            }
        }
        else
        {
            if (t[i] == '1')
                continue;
            else
            {
                z ^= true;
                --kk;
            }
        }
    }
    if (kk == 0)
    {
        return ans;
    }
    kk = k;
    z = true;
    for (int i = 1; i < n; ++i)
    {
        if ((z == false && a[i - 1] == 'L') || (z == true && a[i - 1] == 'R'))
        {
            if (t[i] == '0')
                continue;
            else
            {
                z ^= true;
                --kk;
            }
        }
        else
        {
            if (t[i] == '1')
                continue;
            else
            {
                z ^= true;
                --kk;
            }
        }
    }
    if (kk == 0)
        return ans;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    cin >> a;
    cin >> ll >> rr;
    long long ans = 0;
    for (int i = 0; i < n; ++i)
        t[i] = rr[i];
    ans = solv();
    for (int i = 0; i < n; ++i)
        t[i] = ll[i];
    ans = (ans - solv() + M) % M;
    ans = (ans + stg()) % M;
    cout << ans << endl;
    return 0;
}

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