oj.uz

Submission #119289

# Submission time Handle Problem Language Result Execution time Memory
119289 2019-06-20T23:51:00 Z onjo0127 Ljetopica (COI19_ljetopica) C++11
8 / 100
 55 ms 26844 KB 
#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1e9 + 7;
 
int N;
long long C[1009][1009][2], D[1009][1009][2], bi[1009];
char S[1009], A[1009], B[1009];
 
void go(int idx, int left, bool ok) {
	long long &CC = C[idx][left][ok], &DD = D[idx][left][ok];
 
	if(idx == N) {
		if(left == 0) CC = DD = 1;
		else CC = DD = 0;
		return;
	}
	if(DD != -1) return;
 
	char X = S[idx];
	if(!ok) {
        if(X == 'L') X = 'R';
        else X = 'L';
    }
 
	go(idx+1, left, ok);
	if(left) go(idx+1, left-1, !ok);
 
	CC = C[idx+1][left][ok];
	if(left) CC += C[idx+1][left-1][!ok];
	CC %= MOD;
 
	if(X == 'L') {
		DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx - 1] % MOD;
		DD %= MOD;
		if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx] % MOD, DD %= MOD;
	}
	else {
		DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx] % MOD;
		DD %= MOD;
		if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx - 1] % MOD, DD %= MOD;
	}
}
 
int main() {
    int K; scanf("%d%d",&N,&K);
    bi[0] = 1; for(int i=1; i<=N; i++) bi[i] = bi[i-1] * 2 % MOD;
    scanf(" %s %s %s", S+1, A, B);
   	memset(D, -1, sizeof(D));
    go(1, K, 1); go(1, K, 0);
 
    long long ans = (D[1][K][0] + D[1][K][1]) % MOD; int c1 = 0, c2 = 0;
    //printf("before: %lld\n",ans);
 
    long long x = 1;
    for(int i=1; i<N; i++) {
    	if(A[i] == '1') {
    		if(S[i] == 'R') ++c1;
    		if(S[i] == 'L') ++c2;
            x = x * 2;
 
    		if(c1 <= K)	{
                ans += MOD - (D[i+1][K - c1][(c1 + 1) % 2] + C[i+1][K - c1][(c1 + 1) % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
                //printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c1][(c1 + 1) % 2], C[i+1][K - c1][(c1 + 1) % 2], x - 1, bi[N - i - 1]);
            }
    		ans %= MOD;
    		if(c2 <= K)	{
                ans += MOD - (D[i+1][K - c2][c2 % 2] + C[i+1][K - c2][c2 % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
                //printf("D: %lld\n", D[i+1][K - c2][c2 % 2]);
            }
    		ans %= MOD;
 
            x = x / 2;
    		if(S[i] == 'R') --c1;
    		if(S[i] == 'L') --c2;
    	}
    	if(A[i] == '1') {
            x = (x<<1) | 1;
            x %= MOD;
    		if(S[i] == 'L') ++c1;
    		if(S[i] == 'R') ++c2;
    	}
    	else {
            x = (x<<1);
            x %= MOD;
    		if(S[i] == 'L') ++c2;
    		if(S[i] == 'R') ++c1;
    	}
        //printf("ans: %lld\n", ans);
    }
    //printf("middle: %lld\n", ans);
    c1 = c2 = 0; x = 1;
    for(int i=1; i<N; i++) {
    	if(B[i] == '0') {
    		if(S[i] == 'L') ++c1;
    		if(S[i] == 'R') ++c2;
            x = x*2+1;
 
    		if(c1 <= K)	{
                ans += MOD - (D[i+1][K - c1][(c1 + 1) % 2] + C[i+1][K - c1][(c1 + 1) % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
                //printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c1][(c1 + 1) % 2], C[i+1][K - c1][(c1 + 1) % 2], x - 1, bi[N - i - 1]);
            }
    		ans %= MOD;
    		if(c2 <= K)	{
                ans += MOD - (D[i+1][K - c2][c2 % 2] + C[i+1][K - c2][c2 % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
                //printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c2][c2 % 2], C[i+1][K - c2][c2 % 2], x - 1, bi[N - i - 1]);
            }
    		ans %= MOD;
 
            x = x/2;
    		if(S[i] == 'L') --c1;
    		if(S[i] == 'R') --c2;
    	}
    	if(B[i] == '0') {
            x = (x<<1);
            x %= MOD;
    		if(S[i] == 'R') ++c1;
    		if(S[i] == 'L') ++c2;
    	}
    	else {
            x = (x<<1) | 1;
            x %= MOD;
    		if(S[i] == 'R') ++c2;
    		if(S[i] == 'L') ++c1;
    	}
    }
    printf("%lld", ans);
    return 0; 
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:46:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int K; scanf("%d%d",&N,&K);
            ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s %s %s", S+1, A, B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20344 KB Output is correct
2 Correct 17 ms 20224 KB Output is correct
3 Correct 17 ms 19968 KB Output is correct
4 Correct 17 ms 19832 KB Output is correct
5 Correct 16 ms 19536 KB Output is correct
6 Correct 16 ms 19328 KB Output is correct
7 Correct 16 ms 19200 KB Output is correct
8 Correct 16 ms 18944 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 26844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20344 KB Output is correct
2 Correct 17 ms 20224 KB Output is correct
3 Correct 17 ms 19968 KB Output is correct
4 Correct 17 ms 19832 KB Output is correct
5 Correct 16 ms 19536 KB Output is correct
6 Correct 16 ms 19328 KB Output is correct
7 Correct 16 ms 19200 KB Output is correct
8 Correct 16 ms 18944 KB Output is correct
9 Incorrect 16 ms 16384 KB Output isn't correct
10 Halted 0 ms 0 KB -