# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129845 | pzdba | Ljetopica (COI19_ljetopica) | C++14 | 116 ms | 63352 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
char s[1002], a[1002], b[1002];
ll dp[1002][1002][2][2], cnt[1002][1002][2][2];
int n, k;
int dfs(char *t){
if(t[1] == '0') return 0;
memset(dp, 0, sizeof(dp));
memset(cnt, 0, sizeof(cnt));
dp[1][0][1][0] = 1;
cnt[1][0][1][0] = 1;
dp[1][0][1][1] = 1;
cnt[1][0][1][1] = 1;
bool ok = 0;
for(int i=2;i<=n;i++){
for(int j=0;j<=k;j++){
if(s[i] == 'L'){
dp[i][j][0][0] = (dp[i][j][0][0] + dp[i-1][j][0][0]*2)%mod;
cnt[i][j][0][0] = (cnt[i][j][0][0] + cnt[i-1][j][0][0])%mod;
dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][0][1]*2 + cnt[i-1][j][0][1])%mod;
cnt[i][j][0][1] = (cnt[i][j][0][1] + cnt[i-1][j][0][1])%mod;
if(t[i] == '1'){
dp[i][j][1][1] = (dp[i][j][1][1] + dp[i-1][j][1][1]*2 + cnt[i-1][j][1][1])%mod;
cnt[i][j][1][1] = (cnt[i][j][1][1] + cnt[i-1][j][1][1])%mod;
dp[i][j][0][0] = (dp[i][j][0][0] + dp[i-1][j][1][0]*2)%mod;
cnt[i][j][0][0] = (cnt[i][j][0][0] + cnt[i-1][j][1][0])%mod;
}
else{
dp[i][j][1][0] = (dp[i][j][1][0] + dp[i-1][j][1][0]*2)%mod;
cnt[i][j][1][0] = (cnt[i][j][1][0] + cnt[i-1][j][1][0])%mod;
}
if(j != k){
dp[i][j+1][0][1] = (dp[i][j+1][0][1] + dp[i-1][j][0][0]*2 + cnt[i-1][j][0][0])%mod;
cnt[i][j+1][0][1] = (cnt[i][j+1][0][1] + cnt[i-1][j][0][0])%mod;
dp[i][j+1][0][0] = (dp[i][j+1][0][0] + dp[i-1][j][0][1]*2)%mod;
cnt[i][j+1][0][0] = (cnt[i][j+1][0][0] + cnt[i-1][j][0][1])%mod;
if(t[i] == '1'){
dp[i][j+1][1][1] = (dp[i][j+1][1][1] + dp[i-1][j][1][0]*2 + cnt[i-1][j][1][0])%mod;
cnt[i][j+1][1][1] = (cnt[i][j+1][1][1] + cnt[i-1][j][1][0])%mod;
dp[i][j+1][0][0] = (dp[i][j+1][0][0] + dp[i-1][j][1][1]*2)%mod;
cnt[i][j+1][0][0] = (cnt[i][j+1][0][0] + cnt[i-1][j][1][1])%mod;
}
else{
dp[i][j+1][1][0] = (dp[i][j+1][1][0] + dp[i-1][j][1][1]*2)%mod;
cnt[i][j+1][1][0] = (cnt[i][j+1][1][0] + cnt[i-1][j][1][1])%mod;
}
}
}
else{
dp[i][j][0][0] = (dp[i][j][0][0] + dp[i-1][j][0][0]*2 + cnt[i-1][j][0][0])%mod;
cnt[i][j][0][0] = (cnt[i][j][0][0] + cnt[i-1][j][0][0])%mod;
dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][0][1]*2)%mod;
cnt[i][j][0][1] = (cnt[i][j][0][1] + cnt[i-1][j][0][1])%mod;
if(t[i] == '1'){
dp[i][j][1][0] = (dp[i][j][1][0] + dp[i-1][j][1][0]*2 + cnt[i-1][j][1][0])%mod;
cnt[i][j][1][0] = (cnt[i][j][1][0] + cnt[i-1][j][1][0])%mod;
dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][1][1]*2)%mod;
cnt[i][j][0][1] = (cnt[i][j][0][1] + cnt[i-1][j][1][1])%mod;
}
else{
dp[i][j][1][1] = (dp[i][j][1][1] + dp[i-1][j][1][1]*2)%mod;
cnt[i][j][1][1] = (cnt[i][j][1][1] + cnt[i-1][j][1][1])%mod;
}
if(j != k){
dp[i][j+1][0][1] = (dp[i][j+1][0][1] + dp[i-1][j][0][0]*2)%mod;
cnt[i][j+1][0][1] = (cnt[i][j+1][0][1] + cnt[i-1][j][0][0])%mod;
dp[i][j+1][0][0] = (dp[i][j+1][0][0] + dp[i-1][j][0][1]*2 + cnt[i-1][j][0][1])%mod;
cnt[i][j+1][0][0] = (cnt[i][j+1][0][0] + cnt[i-1][j][0][1])%mod;
if(t[i] == '1'){
dp[i][j+1][1][0] = (dp[i][j+1][1][0] + dp[i-1][j][1][1]*2 + cnt[i-1][j][1][1])%mod;
cnt[i][j+1][1][0] = (cnt[i][j+1][1][0] + cnt[i-1][j][1][1])%mod;
dp[i][j+1][0][1] = (dp[i][j+1][0][1] + dp[i-1][j][1][0]*2)%mod;
cnt[i][j+1][0][1] = (cnt[i][j+1][0][1] + cnt[i-1][j][1][0])%mod;
}
else{
dp[i][j+1][1][1] = (dp[i][j+1][1][1] + dp[i-1][j][1][0]*2)%mod;
cnt[i][j+1][1][1] = (cnt[i][j+1][1][1] + cnt[i-1][j][1][0])%mod;
}
}
}
}
}
return (dp[n][k][0][0] + dp[n][k][0][1] + dp[n][k][1][0] + dp[n][k][1][1])%mod;
}
int main(){
scanf("%d%d", &n, &k);
scanf("%s", s+2);
scanf("%s", a+1);
scanf("%s", b+1);
for(int i=n;i>=1;i--){
if(a[i] == '1'){
a[i] = '0';
for(int j=i+1;j<=n;j++) a[j] = '1';
break;
}
}
int res1 = dfs(b);
int res2 = dfs(a);
printf("%d\n", (res1 - res2 + mod)%mod);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |