Submission #1041694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041694		vjudge1	Ljetopica (COI19_ljetopica)	C++17	0 / 100	10 ms	23900 KiB

ljetopica

#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;
}

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