Submission #491080

#	Time	Username	Problem	Language	Result	Execution time	Memory
491080		rainboy	Ljetopica (COI19_ljetopica)	C11	100 / 100	65 ms	304 KiB

ljetopica

#include <stdio.h>
#include <string.h>

#define N	1000
#define MD	1000000007

int pp2[N + 1];

void init() {
	int i;

	pp2[0] = 1;
	for (i = 1; i <= N; i++)
		pp2[i] = pp2[i - 1] * 2 % MD;
}

int solve(char *aa, char *cc, int n, int k, int lt) {
	static char bb[N + 1];
	static int dp[N + 1][2], dq[N + 1][2];
	int i, j;

	bb[0] = '1';
	for (i = 0; i < n - 1; i++)
		bb[i + 1] = cc[i] == 'L' ? '0' : '1';
	for (j = 0; j <= k; j++)
		dp[j][0] = dp[j][1] = 0, dq[j][0] = dq[j][1] = 0;
	dp[0][0] = 1, dq[0][0] = 0;
	for (i = 0; i < n; i++) {
		int a = aa[i] - '0', b = bb[i] - '0';

		for (j = k; j >= 0; j--) {
			int x0 = dp[j][0], y0 = dq[j][0], x1 = dp[j][1], y1 = dq[j][1], b_;

			dp[j][0] = dp[j][1] = dq[j][0] = dq[j][1] = 0;
			b_ = b ^ j % 2;
			if (b_ != a) {
				dp[j][1] = (dp[j][1] + x1) % MD;
				dq[j][1] = (dq[j][1] + y1 + (long long) pp2[n - 1 - i] * x1 % MD * b_) % MD;
				if (b_ < a) {
					dp[j][1] = (dp[j][1] + x0) % MD;
					dq[j][1] = (dq[j][1] + y0 + (long long) pp2[n - 1 - i] * x0 % MD * b_) % MD;
				}
			} else {
				dp[j][0] = (dp[j][0] + x0) % MD;
				dq[j][0] = (dq[j][0] + y0 + (long long) pp2[n - 1 - i] * x0 % MD * b_) % MD;
				dp[j][1] = (dp[j][1] + x1) % MD;
				dq[j][1] = (dq[j][1] + y1 + (long long) pp2[n - 1 - i] * x1 % MD * b_) % MD;
			}
			if (j < k) {
				b_ = b ^ (j + 1) % 2;
				if (b_ != a) {
					dp[j + 1][1] = (dp[j + 1][1] + x1) % MD;
					dq[j + 1][1] = (dq[j + 1][1] + y1 + (long long) pp2[n - 1 - i] * x1 % MD * b_) % MD;
					if (b_ < a) {
						dp[j + 1][1] = (dp[j + 1][1] + x0) % MD;
						dq[j + 1][1] = (dq[j + 1][1] + y0 + (long long) pp2[n - 1 - i] * x0 % MD * b_) % MD;
					}
				} else {
					dp[j + 1][0] = (dp[j + 1][0] + x0) % MD;
					dq[j + 1][0] = (dq[j + 1][0] + y0 + (long long) pp2[n - 1 - i] * x0 % MD * b_) % MD;
					dp[j + 1][1] = (dp[j + 1][1] + x1) % MD;
					dq[j + 1][1] = (dq[j + 1][1] + y1 + (long long) pp2[n - 1 - i] * x1 % MD * b_) % MD;
				}
			}
		}
	}
	return (dq[k][1] + (lt ? 0 : dq[k][0])) % MD;
}

int main() {
	static char cc[N + 1], aa[N + 1], bb[N + 1];
	int n, k, i, ans;

	init();
	scanf("%d%d%s%s%s", &n, &k, cc, aa, bb);
	ans = (solve(bb, cc, n, k, 0) - solve(aa, cc, n, k, 1)) % MD;
	for (i = 0; i < n - 1; i++)
		cc[i] = cc[i] == 'L' ? 'R' : 'L';
	ans = ((long long) ans + solve(bb, cc, n, k, 0) - solve(aa, cc, n, k, 1)) % MD;
	if (ans < 0)
		ans += MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

ljetopica.c: In function 'main':
ljetopica.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d%s%s%s", &n, &k, cc, aa, bb);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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