제출 #467581

#제출 시각아이디문제언어결과실행 시간메모리
467581couplefireLjetopica (COI19_ljetopica)C++17
100 / 100
227 ms63180 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1005; const int MOD = 1000000007; inline int add(int a, int b){return (a+b>=MOD)?a+b-MOD:a+b;} inline void inc(int& a, int b){a = add(a, b);} inline int sub(int a, int b){return (a-b<0)?a-b+MOD:a-b;} inline void dec(int &a, int b){a = sub(a, b);} inline int mul(int a, int b){return 1ll*a*b%MOD;} inline void grow(int &a, int b){a = mul(a, b);} int n, k, dp1[N][N][2][2][2], dp2[N][N][2][2][2], ans; int moves[N], lo[N], hi[N]; string _str; int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> k >> _str; for(int i = 0; i<n-1; ++i) moves[i] = _str[i]=='L'?0:1; cin >> _str; for(int i = 0; i<n; ++i) lo[i] = _str[i]-'0'; cin >> _str; for(int i = 0; i<n; ++i) hi[i] = _str[i]-'0'; dp1[0][0][1][1][0] = dp1[0][0][1][1][1] = dp2[0][0][1][1][0] = dp2[0][0][1][1][1] = 1; for(int i = 0; i<n-1; ++i) for(int j = 0; j<=k; ++j) for(int a = 0; a<2; ++a) for(int b = 0; b<2; ++b) for(int f = 0; f<2; ++f){ int nxt = moves[i]^f; int v1 = dp1[i][j][a][b][f]; int v2 = dp2[i][j][a][b][f]; if((!a || (nxt>=lo[i+1])) && (!b || (nxt<=hi[i+1]))) inc(dp1[i+1][j][a && nxt==lo[i+1]][b && nxt==hi[i+1]][f], add(mul(v1, 2), mul(nxt==1, v2))), inc(dp2[i+1][j][a && nxt==lo[i+1]][b && nxt==hi[i+1]][f], v2); if(j==k) continue; nxt ^= 1; if((!a || (nxt>=lo[i+1])) && (!b || (nxt<=hi[i+1]))) inc(dp1[i+1][j+1][a && nxt==lo[i+1]][b && nxt==hi[i+1]][f^1], add(mul(v1, 2), mul(nxt==1, v2))), inc(dp2[i+1][j+1][a && nxt==lo[i+1]][b && nxt==hi[i+1]][f^1], v2); } for(int a = 0; a<2; ++a) for(int b = 0; b<2; ++b) for(int c = 0; c<2; ++c) inc(ans, dp1[n-1][k][a][b][c]); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...