#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1005;
int const mod=1e9+7;
int choose[N][N];
int dp[N][N][2];
int pow2[N];
int n,k;
string low,high,com;
void fill_choose(){
for (int i = 0; i < N; ++i)
for(int j=0;j<=i;j++){
if(j==0)
choose[i][j]=1;
else
choose[i][j]=(choose[i-1][j]+choose[i-1][j-1])%mod;
}}
void rvrs(){
for(int i=0;i<n;i++){
if(com[i]=='R')
com[i]='L';
else
com[i]='R';
}}
void fill_dp(){
int len=n-1;
dp[0][0][0]=dp[0][0][1]=pow2[len];
for (int i = 1; i <=len; ++i)
for (int j = 0; j <=k; ++j){
//p==0
if(com[len-i]=='L'){
dp[i][j][0]=dp[i-1][j][0];
if(j>0)
dp[i][j][0]+=(dp[i-1][j-1][1]+(choose[i-1][j-1]*pow2[i-1])%mod)%mod;
dp[i][j][0]%=mod;
}
else{
dp[i][j][0]=(dp[i-1][j][0]+(choose[i-1][j]*pow2[i-1])%mod)%mod;
if(j>0)
dp[i][j][0]+=dp[i-1][j-1][1];
dp[i][j][0]%=mod;
}
//p==1
if(com[len-i]=='R'){
dp[i][j][1]=dp[i-1][j][1];
if(j>0)
dp[i][j][1]+=(dp[i-1][j-1][0]+(choose[i-1][j-1]*pow2[i-1])%mod)%mod;
dp[i][j][1]%=mod;
}
else{
dp[i][j][1]=(dp[i-1][j][1]+(choose[i-1][j]*pow2[i-1])%mod)%mod;
if(j>0)
dp[i][j][1]+=dp[i-1][j-1][0];
dp[i][j][1]%=mod;
}
}}
void fill_pow(){
pow2[0]=1;
for (int i = 1; i < N; ++i)
pow2[i]=(pow2[i-1]*2)%mod;}
int less_than(string s,int pr){
int len=n-1,prev=0,ans=0,used=0;
for(int i=1;i<=len;i++){
bool c=(pr==0 && com[i-1]=='R')||(pr==1 && com[i-1]=='L');
if(s[i]=='0'){
if(c){
used++;
pr^=1;
}
continue;
}
if(used+c<=k){
ans+=prev*(choose[len-i][k-(used+c)]);
ans+=dp[len-i][k-(used+c)][pr^c];
}
prev+=pow2[len-i];
}
return ans;}
bool check(string s,int pr){
int used=0;
for (int i = 1; i < n; ++i)
{
bool c=(pr==0 && com[i]=='R')||(pr==1 && com[i]=='L');
if(s[i]=='0')
used+=c;
else
used+=c^1;
}
return (used==k);
}
signed main(){
fill_choose();
//input
cin>>n>>k;
cin>>com>>low>>high;
//solve
fill_pow();fill_dp();
// int ans=(pow2[n]*(choose[n-1][k]))%mod;
int ans=((less_than(high,0)-less_than(low,0))+mod)%mod;
ans+=((less_than(high,1)-less_than(low,1))+mod)%mod;
ans%=mod;
if(check(high,0)||check(high,1)){
for(int i=1;i<=n;i++)
if(high[i-1]=='1')
ans=(ans+pow2[n-i])%mod;
}
cout<<ans%mod<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
