Submission #238656

#	Time	Username	Problem	Language	Result	Execution time	Memory
238656		Kastanda	Ljetopica (COI19_ljetopica)	C++11	100 / 100	28 ms	18176 KiB

ljetopica

// Criminal
#include<bits/stdc++.h>
using namespace std;
const int N = 1009, Mod = 1e9 + 7;
int n, k, Pw[N], C[N][N];
pair < int , int > dp[2][N][N];
string A, B, D, E;
inline int Diff(string s, string d, int l = n - 1)
{
    int Cnt = 0;
    for (int i = 0; i < l; i ++)
        Cnt += (d[i] != s[i]) ^ (Cnt & 1);
    return Cnt;
}
inline int Get(string s, int l)
{
    int df1 = Diff(s, D, l);
    int df2 = Diff(s, E, l);
    int tot = 0;
    if (df1 <= k)
    {
        for (int i = 0; i < l; i ++)
            if (s[i] == '1')
                tot = (tot + Pw[n - 2 - i] * 1LL * C[k - df1][n - 1 - l]) % Mod;
        tot = (tot + Pw[n - 1] * 1LL * C[k - df1][n - 1 - l]) % Mod;
        tot = (tot + dp[0][l][k - df1].first) % Mod;
    }
    if (df2 <= k)
    {
        for (int i = 0; i < l; i ++)
            if (s[i] == '1')
                tot = (tot + Pw[n - 2 - i] * 1LL * C[k - df2][n - 1 - l]) % Mod;
        tot = (tot + Pw[n - 1] * 1LL * C[k - df2][n - 1 - l]) % Mod;
        tot = (tot + dp[1][l][k - df2].first) % Mod;
    }
    return (tot);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k >> D >> A >> B;
    A = A.substr(1); B = B.substr(1); E = D;
    for (int i = 0; i < (int)D.size(); i ++)
        D[i] = (D[i] == 'L' ? '0' : '1'),
        E[i] = (E[i] == 'R' ? '0' : '1');

    for (int i = Pw[0] = 1; i < N; i ++)
        Pw[i] = Pw[i - 1] * 2LL % Mod;
    for (int i = 0; i < N; i ++)
        for (int j = C[0][i] = C[i][i] = 1; j < i; j ++)
            C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % Mod;

    for (int w = 0; w < 2; w ++)
    {
        string d = w ? E : D;
        dp[w][n - 1][0] = {0, 1};
        for (int i = n - 2; ~ i; i --)
            for (int j = 0; i + j <= n - 1 && j <= k; j ++)
            {
                dp[w][i][j].first = dp[w][i + 1][j].first;
                dp[w][i][j].second = dp[w][i + 1][j].second;
                if (j)
                {
                    dp[w][i][j].first = (dp[w][i][j].first + dp[w][i + 1][j - 1].first) % Mod;
                    dp[w][i][j].second = (dp[w][i][j].second + dp[w][i + 1][j - 1].second) % Mod;
                }
                if ((d[i] - '0') ^ (k - j & 1))
                    dp[w][i][j].first = (dp[w][i][j].first + Pw[n - 2 - i] * 1LL * dp[w][i + 1][j].second) % Mod;
                else if (j)
                    dp[w][i][j].first = (dp[w][i][j].first + Pw[n - 2 - i] * 1LL * dp[w][i + 1][j - 1].second) % Mod;
            }
    }

    if (A == B)
    {
        if (Diff(A, D) != k && Diff(A, E) != k)
            return !printf("0\n");
        int tot = 0;
        for (int i = 0; i < n - 1; i ++)
            if (A[i] == '1')
                tot = (tot + Pw[n - 1 - i - 1]) % Mod;
        tot = (tot + Pw[n - 1]) % Mod;
        return !printf("%d\n", tot);
    }
    int i = 0;
    while (A[i] == B[i])
        i ++;
    assert(A[i] == '0');
    int tot = 0;
    if (Diff(A, D) == k || Diff(A, E) == k)
    {
        for (int i = 0; i < n - 1; i ++)
            if (A[i] == '1')
                tot = (tot + Pw[n - 1 - i - 1]) % Mod;
        tot = (tot + Pw[n - 1]) % Mod;
    }
    if (Diff(B, D) == k || Diff(B, E) == k)
    {
        for (int i = 0; i < n - 1; i ++)
            if (B[i] == '1')
                tot = (tot + Pw[n - 1 - i - 1]) % Mod;
        tot = (tot + Pw[n - 1]) % Mod;
    }
    i ++;
    while (i < n - 1)
    {
        if (A[i] == '0')
        {
            string s = A;
            s[i] = '1';
            tot = (tot + Get(s, i + 1)) % Mod;
        }
        if (B[i] == '1')
        {

            string s = B;
            s[i] = '0';
            tot = (tot + Get(s, i + 1)) % Mod;
        }
        i ++;
    }
    return !printf("%d\n", tot);
}

Compilation message (stderr)

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:68:39: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                 if ((d[i] - '0') ^ (k - j & 1))
                                     ~~^~~

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