#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll dp[1007][1007][2], pw[10007];
ll sum[1007][1007][2];
ll const mod = (ll)(1e9 + 7);
ll get(string &a, string b, ll n, ll k, bool inclusive){
for(int i = 0; i <= n + 1; i++)
for(int j = 0; j <= k + 1; j++)
dp[i][j][0] = dp[i][j][1] = 0;
dp[n][0][1] = 1;
dp[n][1][0] = 1;
dp[n][0][0] = 1;
dp[n][1][1] = 1;
if(a[n] == '0'){
sum[n][0][1] = 1;
sum[n][1][0] = 1;
}
else{
sum[n][0][0] = 1;
sum[n][1][1] = 1;
}
for(int i = n - 1; i >= 1; i--){
for(int j = 0; j <= k + 1; j++){
// no add inverse:
// inverse before:
char c = (a[i] == '0' ? '1' : '0');
sum[i][j][1] = (((c == '0' ? 0 : pw[n - i]) * dp[i + 1][j][1]) % mod + sum[i + 1][j][1]) % mod;
dp[i][j][1] = dp[i + 1][j][1];
// no inverse before
sum[i][j][0] = (((a[i] == '0' ? 0 : pw[n - i]) * dp[i + 1][j][0]) % mod + sum[i + 1][j][0]) % mod;
dp[i][j][0] = dp[i + 1][j][0];
// add inverse:
if(j != 0 && i != 1){
// inverse before = 0 inverse
sum[i][j][1] = (sum[i][j][1] + (((a[i] == '0' ? 0 : pw[n - i]) * dp[i + 1][j - 1][0]) % mod + sum[i + 1][j - 1][0]) % mod) % mod;
dp[i][j][1] = (dp[i][j][1] + dp[i + 1][j - 1][0]) % mod;
// no inverse before
char c = (a[i] == '0' ? '1' : '0');
sum[i][j][0] = (sum[i][j][0] + (((c == '0' ? 0 : pw[n - i]) * dp[i + 1][j - 1][1]) % mod + sum[i + 1][j - 1][1]) % mod) % mod;
dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j - 1][1]) % mod;
}
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 0; j <= k; j++){
// cout << i << ' ' << j << ": " << dp[i][j][0] << ' ' << dp[i][j][1] << endl;
// }
// cout << endl << endl;
// }
//
// cout << "_____________" << endl;
//
// for(int i = 1; i <= n; i++){
// for(int j = 0; j <= k; j++){
// cout << i << ' ' << j << ": " << sum[i][j][0] << ' ' << sum[i][j][1] << endl;
// }
// cout << endl << endl;
// }
ll ans = 0, need = 0, last = 0;
ll cur = pw[n];
for(int i = 1; i <= n; i++){
// i = first position < b[i]
if(b[i] == '0'){
if(a[i] != b[i]){
if(last == 0){
need++;
}
last = 1;
}
else{
if(last == 1)
need++;
last = 0;
}
continue;
}
ll need2 = need;
ll last2 = last;
if(a[i] == '0'){
if(last == 1){
need2++;
}
last2 = 0;
}
else{
if(last == 0){
need2++;
}
last2 = 1;
}
ll left0 = k - need2;
//cout << " " << i << ' ' << left0 << ' ' << last2 << endl;
if(left0 >= 0){
bool firstinversion = false;
if(i == 1){
if(a[1] == '1')
firstinversion = true;
}
else{
if(a[1] != b[1])
firstinversion = true;
}
ll possible = left0 - (firstinversion ? -1 : 1);
ll cnt = 0;
if(i == n){
if(left0 == 0 || possible == 0){
cnt = cur;
}
}
else{
cnt = (cur * dp[i + 1][left0][last2]) % mod;
cnt = (cnt + sum[i + 1][left0][last2]) % mod;
//cout << "!! " << i << ' ' << left0 << ' ' << dp[i + 1][left0][last2] << ' ' << sum[i + 1][left0][last2] << ' ' << cnt << endl;
if(possible >= 0){
ll cnt2 = ((cur * dp[i + 1][possible][last2]) % mod) % mod;
cnt2 = (cnt2 + sum[i + 1][possible][last2]) % mod;
cnt = (cnt + cnt2) % mod;
//cout << "?? " << i << ' ' << possible << ' ' << dp[i + 1][possible][last2] << ' ' << sum[i + 1][possible][last2] << ' ' << cnt2 << endl;
}
}
ans = (ans + cnt) % mod;
//cout << cnt << endl;
}
//cout << "last " << last << endl;
if(a[i] != b[i]){
if(last == 0){
need++;
}
last = 1;
}
else{
if(last == 1){
need++;
}
last = 0;
}
cur += (b[i] == '0' ? 0 : pw[n - i]);
}
// cout << need << ' ' << cur << ' '<< (k - need)<< endl;
if(inclusive){
if(k - need == 0){
ans = (ans + cur) % mod;
}
else{
bool firstinversion = false;
if(a[1] != b[1])
firstinversion = true;
ll possible = k - need - (firstinversion ? -1 : 1);
if(possible == 0)
ans = (ans + cur) % mod;
}
}
return ans;
}
int main(){
pw[0] = 1;
for(int i = 1; i <= 1001; i++)
pw[i] = (pw[i - 1] * 2) % mod;
ll n, k;
cin >> n >> k;
n--;
string a;
cin >> a;
for(auto &i: a)
i = (i == 'L' ? '0' : '1');
a = '#' + a;
string b, c;
cin >> b >> c;
auto h2 = get(a, c, n, k, true);
// cout << h2 << endl;
//
// return 0;
////
auto h1 = get(a, b, n, k, false);
ll ans = (h2 - h1) % mod;
if(ans < 0)
ans += mod;
cout << ans << endl;
return 0;
}
/*
4 0
RLL
1011
1111
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31320 KB |
Output is correct |
| 2 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
29020 KB |
Output is correct |
| 6 |
Correct |
3 ms |
26972 KB |
Output is correct |
| 7 |
Correct |
2 ms |
26972 KB |
Output is correct |
| 8 |
Correct |
2 ms |
22876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4548 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
31836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31320 KB |
Output is correct |
| 2 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
29020 KB |
Output is correct |
| 6 |
Correct |
3 ms |
26972 KB |
Output is correct |
| 7 |
Correct |
2 ms |
26972 KB |
Output is correct |
| 8 |
Correct |
2 ms |
22876 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4548 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
