Submission #706954

#TimeUsernameProblemLanguageResultExecution timeMemory
706954NursikLjetopica (COI19_ljetopica)C++14
8 / 100
42 ms31700 KiB
#include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <unordered_set> #include <unordered_map> #include <stdio.h> #include <bitset> #include <cstdint> #include <cassert> #include <functional> #include <complex> #include <random> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double const ll maxn = 1e3 + 1, maxm = 1e3 + 1; const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31; const ld eps = 1e-9; int n, k; string s, l, r; ll dp[maxn][maxn][2][2]; void add(ll &x, ll y){ x += y; x %= mod; } ll get(string lim){ memset(dp, 0, sizeof(dp)); ll sum = 0; lim = '#' + lim; dp[1][0][0][1] = 1; dp[1][0][1][1] = 1; int m = (int)lim.size(); for (int i = 1; i < m - 1; ++i){ for (int j = 0; j <= k; ++j){ for (int fl = 0; fl < 2; ++fl){ for (int flg = 0; flg < 2; ++flg){ if (dp[i][j][fl][flg] > 0){ int ni = i + 1, nj = j, nfl = fl, nflg = flg; if (s[i - 1] == 'L'){ if (fl == 0){ if (lim[i + 1] == '1'){ nflg = 0; } add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } else{ if (lim[i + 1] == '1' || nflg == 0){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } } else{ if (fl == 0){ if (lim[i + 1] == '1' || nflg == 0){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } else{ if (lim[i + 1] == '1'){ nflg = 0; } add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } ni = i + 1, nj = j + 1, nfl = fl, nflg = flg; if (j + 1 <= k){ nfl ^= 1; if (s[i - 1] == 'L'){ if (fl == 0){ if (lim[i + 1] == '1'){ nflg = 0; } add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } else{ if (lim[i + 1] == '1' || nflg == 0){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } } else{ if (fl == 0){ if (lim[i + 1] == '1' || nflg == 0){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } else{ if (lim[i + 1] == '1'){ nflg = 0; } add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } } } } } } } for (int i = 0; i < 2; ++i){ for (int j = 0; j < 2; ++j){ sum = (sum + dp[m - 1][k][i][j]) % mod; } } return sum; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; cin >> s; cin >> l >> r; ll ans = (get(r) - get(l) + mod) % mod; memset(dp, 0, sizeof(dp)); string lim = l; lim = '#' + lim; dp[1][0][0][1] = 1; dp[1][0][1][1] = 1; int m = (int)lim.size(); for (int i = 1; i < m - 1; ++i){ for (int j = 0; j <= k; ++j){ for (int fl = 0; fl < 2; ++fl){ for (int flg = 0; flg < 2; ++flg){ if (dp[i][j][fl][flg] > 0){ int ni = i + 1, nj = j, nfl = fl, nflg = flg; if (s[i - 1] == 'L'){ if (fl == 0){ if (lim[i + 1] == '0'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } else{ if (lim[i + 1] == '1'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } } else{ if (fl == 0){ if (lim[i + 1] == '1'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } else{ if (lim[i + 1] == '0'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } } if (j + 1 <= k){ nfl ^= 1; nj = j + 1; if (s[i - 1] == 'L'){ if (fl == 0){ if (lim[i + 1] == '0'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } else{ if (lim[i + 1] == '1'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } } else{ if (fl == 0){ if (lim[i + 1] == '1'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2 + 1); } } else{ if (lim[i + 1] == '0'){ add(dp[ni][nj][nfl][nflg], dp[i][j][fl][flg] * 2); } } } } } } } } } for (int i = 0; i < 2; ++i){ ans = (ans + dp[m - 1][k][i][1]) % mod; } cout << ans; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...