Submission #113380

#	Time	Username	Problem	Language	Result	Execution time	Memory
113380		popovicirobert	Ljetopica (COI19_ljetopica)	C++14	100 / 100	61 ms	16168 KiB

ljetopica

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = (int) 1e9 + 7;
const int MAXN = 1000;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(string &str, int x) {
    reverse(str.begin(), str.end());

    int i = 0;
    while(str[i] == 0) {
        str[i] = 9;
        i++;
    }
    str[i]--;

    while(str.size() && str.back() == 0) {
        str.pop_back();
    }

    reverse(str.begin(), str.end());
}

string str;
int n, k;

int dp[MAXN + 1][MAXN + 1][2];
int cnt[MAXN + 1][MAXN + 1][2];

inline int solve(string &s) {

    if(s.size() < n) {
        return 0;
    }

    for(int i = 1; i < n; i++) {
        s[i - 1] = s[i];
    }

    int ans = 0;

    for(int t = 0; t < 2; t++) {

        for(auto &it : str) {
            it ^= 1;
        }

        memset(dp, 0, sizeof(dp));
        memset(cnt, 0, sizeof(cnt));

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

        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j <= i; j++) {
                for(int jj = 0; jj < 2; jj++) {

                    if((j + jj) & 1) {
                        str[i] ^= 1;
                    }

                    if(s[i] == 0) {
                        if(str[i] == 0) {
                            add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0]) % MOD);
                            add(cnt[i + 1][j + jj][0], cnt[i][j][0]);

                            add(dp[i + 1][j + jj][1], (2LL * dp[i][j][1]) % MOD);
                            add(cnt[i + 1][j + jj][1], cnt[i][j][1]);
                        }
                        else {
                            add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0] + cnt[i][j][0]) % MOD);
                            add(cnt[i + 1][j + jj][0], cnt[i][j][0]);
                        }
                    }
                    else {
                        if(str[i] == 0) {
                            add(dp[i + 1][j + jj][0], (2LL * (dp[i][j][0] + dp[i][j][1])) % MOD);
                            add(cnt[i + 1][j + jj][0], (cnt[i][j][0] + cnt[i][j][1]) % MOD);
                        }
                        else {
                            add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0] + cnt[i][j][0]) % MOD);
                            add(cnt[i + 1][j + jj][0], cnt[i][j][0]);

                            add(dp[i + 1][j + jj][1], (2LL * dp[i][j][1] + cnt[i][j][1]) % MOD);
                            add(cnt[i + 1][j + jj][1], cnt[i][j][1]);
                        }
                    }

                    if((j + jj) & 1) {
                        str[i] ^= 1;
                    }
                }
            }
        }

        ans = (1LL * ans + dp[n - 1][k][0] + dp[n - 1][k][1]) % MOD;

    }

    return ans;
}


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    //int ;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string l, r;

    cin >> n >> k >> str >> l >> r;

    for(auto &it : str) {
        if(it == 'L') it = 0;
        else it = 1;
    }

    for(auto &it : l) {
        it -= '0';
    }
    for(auto &it : r) {
        it -= '0';
    }

    sub(l, 1);

    int ans = solve(r);
    ans = (ans + MOD - solve(l)) % MOD;

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'int solve(std::__cxx11::string&)':
ljetopica.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size() < n) {
        ~~~~~~~~~^~~

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