Submission #1041644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041644		vjudge1	Ljetopica (COI19_ljetopica)	C++17	17 / 100	11 ms	24156 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 subtract(){
	//low--
	for(int i=n-1;i>=0;i--){
		if(low[i]=='0')
			low[i]='1';
		else{
			low[i]='0';
			break;
		}
	}}
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;
	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-1]=='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;}

signed main(){
	fill_choose();
	//input
	cin>>n>>k;
	cin>>com>>low>>high;
	//solve
	subtract();fill_pow();fill_dp();
	// for(int i=0;i<n;i++)
	// 	for(int j=0;j<=k;j++)
	// 		cout<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<endl;
	int ans=(pow2[n]*(choose[n-1][k]))%mod;
	ans+=(dp[n-1][k][0]+dp[n-1][k][1])%mod;
	ans%=mod;
	// int ans=((less_than(high,0)-less_than(low,0))+mod)%mod;
	// ans+=((less_than(high,1)-less_than(low,1))+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

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