Submission #289399

#	Time	Username	Problem	Language	Result	Execution time	Memory
289399		AMO5	Ljetopica (COI19_ljetopica)	C++17	100 / 100	234 ms	39744 KiB

ljetopica

//modified from koosaga's solution
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=1e3+5;
bool DEBUG=0;

bitset<mxn>bs;
string s,t,a,b;
ll ans=0ll;
int n,k;
vll pw2;
bool vis[mxn][mxn][2][2];
pll dp[mxn][mxn][2][2]; //res, cnt of '1'

ll add(ll a, ll b){
	a%=MOD; b%=MOD;
	a+=b;
	if(a>=MOD)a-=MOD;
	if(a<0)a+=MOD;
	return a;
}

void init(int n){
	pw2.resize(n+1);
	pw2[0]=1ll;
	for(int i=1; i<=n; i++){
		pw2[i]=pw2[i-1]*2ll%MOD;
	}
	return;
}

pll f(int ptr, int left, bool match1, bool match2){
	if(left<0)return pll(0,0);
	if(ptr==n)return pll(0,left==0);
	if(vis[ptr][left][match1][match2])return dp[ptr][left][match1][match2];
	pll res(0,0);
	{
		bool nxtmatch = s[ptr]=='0';
		int kr = match1!=nxtmatch;
		pll r = f(ptr+1,left-kr,nxtmatch,bool(match2&(t[ptr]=='0')));
		res.fi = add(res.fi,r.fi);
		res.se = add(res.se,r.se);
	}
	if(match2==0||t[ptr]=='1'){
		bool nxtmatch = s[ptr]=='1';
		int kr = match1!=nxtmatch;
		pll r = f(ptr+1,left-kr,nxtmatch,match2);
		res.fi = add(res.fi,r.fi);
		res.fi = add(res.fi,r.se*pw2[n-1-ptr]);
		res.se = add(res.se,r.se);
	}
	//cerr<<ptr<<" "<<left<<" "<<match1<<" "<<match2<<": "<<res.fi<<" "<<res.se<<"\n";
	vis[ptr][left][match1][match2]=1;
	return dp[ptr][left][match1][match2]=res;
}

ll solve(string x){
	t=x;
	memset(vis,0,sizeof(vis));
	pll res1 = f(1,k,1,1);
	pll res2 = f(1,k,0,1);
	//cerr<<x<<" "<<res1.fi<<" "<<res1.se<<" "<<res2.fi<<" "<<res2.se<<"\n";
	res1.fi = add(res1.fi,res2.fi);
	res1.se = add(res1.se,res2.se);
	res1.fi = add(res1.fi, res1.se*pw2[n-1]);
	return res1.fi;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>n>>k;
    cin>>s>>a>>b;
    s="R"+s;
    for(int i=0; i<n; i++)
		if(s[i]=='L')s[i]='0';
		else s[i]='1';
    init(n);
    a.back()--;
    for(int i=n-1; i>=0; i--){
		if(a[i]<'0'){
			a[i-1]--;
			a[i]='1';
		}else break;
	}
	//cerr<<a<<" "<<b<<"\n";
	ans = solve(b);
	//cerr<<ans<<"\n";
	if(a[0]=='1'){
		ans = add(ans,MOD-solve(a));
	}
	cout<<ans<<"\n";
	return 0;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61