Submission #239550

#	Time	Username	Problem	Language	Result	Execution time	Memory
239550		kshitij_sodani	Ljetopica (COI19_ljetopica)	C++17	100 / 100	105 ms	31872 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
llo n,k;
llo it[1001];
llo mod=1000000007;
llo pre[1001];
llo st=1;
llo dp[1001][1002][2];
llo co[1001][1002][2];
llo solve(llo cc[]){
	//1-less
	//0-same
	memset(dp,0,sizeof(dp));
	memset(co,0,sizeof(co));
	
	co[0][0][0]=1;
	dp[0][0][0]=1;
//	dp[0][0][1];
//	dp[0][1][0];
	//dp[0][1][1];
	for(llo i=1;i<n;i++){
		for(llo l=0;l<min(k+1,i+1);l++){
			if((it[i-1]+l)%2==0){
				if(cc[i]==0){
					for(llo j=l;j>=0 and j>=l-1;j--){
						co[i][l][1]+=co[i-1][j][1];
						co[i][l][1]%=mod;

						dp[i][l][1]+=dp[i-1][j][1]*2;
						dp[i][l][1]%=mod;

						co[i][l][0]+=co[i-1][j][0];
						co[i][l][0]%=mod;

						dp[i][l][0]+=dp[i-1][j][0]*2;
						dp[i][l][0]%=mod;
						
					}
				}
				else{	
					for(llo j=l;j>=0 and j>=l-1;j--){
						co[i][l][1]+=co[i-1][j][1]+co[i-1][j][0];
						dp[i][l][1]+=2*(dp[i-1][j][1]+dp[i-1][j][0]);
						dp[i][l][1]%=mod;
						co[i][l][1]%=mod;

					}
				}
			}
			else{
				if(cc[i]==0){
					for(llo j=l;j>=0 and j>=l-1;j--){
						co[i][l][1]+=co[i-1][j][1];
						dp[i][l][1]+=2*dp[i-1][j][1]+co[i-1][j][1];
						co[i][l][1]%=mod;
						dp[i][l][1]%=mod;
					}
				}
				else{
					for(llo j=l;j>=0 and j>=l-1;j--){
						co[i][l][1]+=co[i-1][j][1];
						dp[i][l][1]+=dp[i-1][j][1]*2+co[i-1][j][1];
						co[i][l][1]%=mod;
						dp[i][l][1]%=mod;

						co[i][l][0]+=co[i-1][j][0];
						dp[i][l][0]+=2*dp[i-1][j][0]+co[i-1][j][0];
						co[i][l][0]%=mod;
						dp[i][l][0]%=mod;
					}
				}
			}
		}
	}
	llo kk=0;
	kk+=dp[n-1][k][1];
/*	for(llo i=0;i<n;i++){
		for(llo j=0;j<k+1;j++){
			cout<<dp[i][j][0]<<",";
		}
		cout<<endl;
	}
	cout<<endl;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<k+1;j++){
			cout<<dp[i][j][1]<<",";
		}
		cout<<endl;
	}*/
	if(st){
		kk+=dp[n-1][k][0];
	}
	return kk;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	pre[0]=1;
	for(llo i=1;i<n+1;i++){
		pre[i]=pre[i-1]*2;
		pre[i]%=mod;
	}
	llo aa[n];
	llo bb[n];
	string s;
	cin>>s;
	for(llo i=0;i<n-1;i++){
		if(s[i]=='L'){
			it[i]=0;
		}
		else{
			it[i]=1;
		}
	}
	cin>>s;
	for(llo i=0;i<n;i++){
		if(s[i]=='0'){
			aa[i]=0;
		}
		else{
			aa[i]=1;
		}
	}
	cin>>s;
	for(llo i=0;i<n;i++){
		if(s[i]=='0'){
			bb[i]=0;
		}
		else{
			bb[i]=1;
		}
	}
	llo ans=0;
/*
	for(llo i=n-1;i>=0;i--){
		if(aa[i]==1){
			for(llo j=i+1;j<n;j++){
				aa[j]=1;
			}
			aa[i]=0;
			break;
		}
	}*/
	ans+=solve(bb);
	st=0;
//	cout<<ans<<endl;
	ans-=solve(aa);
//	cout<<ans<<endl;

	for(llo i=0;i<n;i++){
		it[i]=1-it[i];
	}
	st=1;
	ans+=solve(bb);
//	cout<<ans<<endl;
	st=0;
	ans-=solve(aa);
//	cout<<ans<<endl;

	ans+=2*mod;
	ans%=mod;
	cout<<ans<<endl;





	return 0;
}

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