Submission #587048

#	Time	Username	Problem	Language	Result	Execution time	Memory
587048		eecs	Ljetopica (COI19_ljetopica)	C++17	100 / 100	187 ms	476 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010, P = 1000000007;
int n, K, pw[maxn];
string dir, A, B;

typedef array<int, 2> arr;
arr f[maxn][2][2][2], g[maxn][2][2][2];

void operator += (arr &A, const arr &B) {
    A = {(A[0] + B[0]) % P, (A[1] + B[1]) % P};
}
arr operator * (const arr &A, const arr &B) {
    return {1LL * A[0] * B[0] % P, (1LL * A[0] * B[1] + 1LL * A[1] * B[0]) % P};
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> K;
    for (int i = pw[0] = 1; i < n; i++) {
        pw[i] = 2 * pw[i - 1] % P;
    }
    cin >> dir >> A >> B;
    f[0][0][0][0] = f[0][1][0][0] = {1, pw[n - 1]};
    for (int i = 0; i < n - 1; i++) {
        memset(g, 0, sizeof(g));
        for (int j = 0; j <= K; j++) for (int k : {0, 1}) {
            for (int a : {0, 1}) for (int b : {0, 1}) {
                for (int l : {0, 1}) {
                    char c = (dir[i] == 'L') ^ k ^ l ? '0' : '1';
                    if (!a && c < A[i + 1]) continue;
                    if (!b && c > B[i + 1]) continue;
                    g[j + l][k ^ l][a | (c > A[i + 1])][b | (c < B[i + 1])]
                        += f[j][k][a][b] * arr{1, (c - '0') * pw[n - i - 2]};
                }
            }
        }
        swap(f, g);
    }
    int ans = 0;
    for (int i : {0, 1}) for (int j : {0, 1}) for (int k : {0, 1}) {
        (ans += f[K][i][j][k][1]) %= P;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'arr operator*(const arr&, const arr&)':
ljetopica.cpp:15:31: warning: narrowing conversion of '(((1 * ((long long int)((int)(& A)->std::array<int, 2>::operator[](0)))) * ((long long int)((int)(& B)->std::array<int, 2>::operator[](0)))) % ((long long int)((int)P)))' from 'long long int' to 'int' [-Wnarrowing]
   15 |     return {1LL * A[0] * B[0] % P, (1LL * A[0] * B[1] + 1LL * A[1] * B[0]) % P};
      |             ~~~~~~~~~~~~~~~~~~^~~
ljetopica.cpp:15:76: warning: narrowing conversion of '((((1 * ((long long int)((int)(& A)->std::array<int, 2>::operator[](0)))) * ((long long int)((int)(& B)->std::array<int, 2>::operator[](1)))) + ((1 * ((long long int)((int)(& A)->std::array<int, 2>::operator[](1)))) * ((long long int)((int)(& B)->std::array<int, 2>::operator[](0))))) % ((long long int)((int)P)))' from 'long long int' to 'int' [-Wnarrowing]
   15 |     return {1LL * A[0] * B[0] % P, (1LL * A[0] * B[1] + 1LL * A[1] * B[0]) % P};
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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