oj.uz

답안 #1041750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041750 2024-08-02T07:45:12 Z vjudge1 Ljetopica (COI19_ljetopica) C++17
22 / 100
 7 ms 23900 KB 
#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];
		}
		if(c==0){
			pr^=1;
			used++;
		}
		prev+=pow2[len-i];
	}
	return ans;
}
signed main(){
	fill_choose();
	//input
	cin>>n>>k;
	cin>>com>>low>>high;
	if(low>high){
		cout<<0<<endl;
		return 0;
	}
	//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;
	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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 3 ms 23900 KB Output is correct
4 Correct 3 ms 23900 KB Output is correct
5 Correct 3 ms 23900 KB Output is correct
6 Correct 3 ms 21852 KB Output is correct
7 Correct 3 ms 21972 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 3 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11708 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 3 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct
12 Correct 3 ms 11612 KB Output is correct
13 Correct 3 ms 11612 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 2 ms 11608 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 23896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 3 ms 23900 KB Output is correct
4 Correct 3 ms 23900 KB Output is correct
5 Correct 3 ms 23900 KB Output is correct
6 Correct 3 ms 21852 KB Output is correct
7 Correct 3 ms 21972 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 3 ms 11612 KB Output is correct
12 Correct 2 ms 11612 KB Output is correct
13 Correct 2 ms 11708 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 2 ms 11612 KB Output is correct
16 Correct 3 ms 11612 KB Output is correct
17 Correct 2 ms 11612 KB Output is correct
18 Correct 2 ms 11612 KB Output is correct
19 Correct 2 ms 11608 KB Output is correct
20 Correct 3 ms 11612 KB Output is correct
21 Correct 3 ms 11612 KB Output is correct
22 Correct 2 ms 11612 KB Output is correct
23 Correct 2 ms 11608 KB Output is correct
24 Incorrect 7 ms 23896 KB Output isn't correct
25 Halted 0 ms 0 KB -