Submission #234586

#	Time	Username	Problem	Language	Result	Execution time	Memory
234586		pedy4000	Ljetopica (COI19_ljetopica)	C++14	100 / 100	90 ms	39160 KiB

ljetopica

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e3 + 3, MOD = 1e9 + 7;
int n, k, ans;
string s, L, R;
char c;
int dp[N][N][2][2][2];
int sum[N][N][2][2][2];

int _sum(int a, int b) {
	int c = a + b;
	if (MOD <= c)
		c -= MOD;
	return c;
}

int _mul(int a, int b) {
	int c = 1LL * a * b % MOD;
	return c;
}

int _pow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1) {
		if (b & 1)
			res = _mul(res, a);
		a = _mul(a, a);
	}
	return res;
}

int calc(string a, string l, string r) {
	a = '0' + a;
	l = '0' + l;
	r = '0' + r;
	dp[0][0][0][1][1] = 1;
	sum[0][0][0][1][1] = 0;
	dp[0][0][1][1][1] = 1;
	sum[0][0][1][1][1] = 0;

	for (int i = 1; i < n; i++)
		for (int j = 0; j <= min(i, k); j++)
			for (int rev = 0; rev < 2; rev++)
				for (int m1 = 0; m1 < 2; m1++)
					for (int m2 = 0; m2 < 2; m2++) {
						dp[i][j][rev][m1][m2] = 0;
						sum[i][j][rev][m1][m2] = 0;
						c = a[i];
						if (rev)
							c = '0' + (a[i] == '0');
						if (m1 && l[i] != c)
							continue;
						if (m2 && r[i] != c)
							continue;
						for (int M1 = 1; M1 >= m1; M1--)
							for (int M2 = 1; M2 >= m2; M2--) {
								if (m1 != M1 && l[i] == c)
									continue;
								if (m2 != M2 && r[i] == c)
									continue;
								if (m1 != M1 && c == '0')
									continue;
								if (m2 != M2 && c == '1')
									continue;

								// if (i == 3 && j == 2 && rev == 0 && m1 == 0 && m2 == 0)
								// 	cout << "! " << dp[i - 1][j][rev][M1][M2] << " " << rev << " " << M1 << " " << M2 << "\n";
								dp[i][j][rev][m1][m2] = _sum(dp[i][j][rev][m1][m2], dp[i - 1][j][rev][M1][M2]);
								sum[i][j][rev][m1][m2] = _sum(sum[i][j][rev][m1][m2], _mul(sum[i - 1][j][rev][M1][M2], 2));
								if (c == '1')
									sum[i][j][rev][m1][m2] = _sum(sum[i][j][rev][m1][m2], dp[i - 1][j][rev][M1][M2]);
							}

						if (!j)
							continue;

						for (int M1 = 1; M1 >= m1; M1--)
							for (int M2 = 1; M2 >= m2; M2--) {
								if (m1 != M1 && l[i] == c)
									continue;
								if (m2 != M2 && r[i] == c)
									continue;
								if (m1 != M1 && c == '0')
									continue;
								if (m2 != M2 && c == '1')
									continue;

								// if (i == 3 && j == 2 && rev == 0 && m1 == 0 && m2 == 0)
								// 	cout << "!! " << m2 << " " << M2 << " " << c << "\n";
								dp[i][j][rev][m1][m2] = _sum(dp[i][j][rev][m1][m2], dp[i - 1][j - 1][1 - rev][M1][M2]);
								sum[i][j][rev][m1][m2] = _sum(sum[i][j][rev][m1][m2], _mul(sum[i - 1][j - 1][1 - rev][M1][M2], 2));
								if (c == '1')
									sum[i][j][rev][m1][m2] = _sum(sum[i][j][rev][m1][m2], dp[i - 1][j - 1][1 - rev][M1][M2]);
							}
					}

	// cout << a << "\n" << l << "\n" << r << "\n";
	int res = 0, cnt = 0;
	for (int rev = 0; rev < 2; rev++)
		for (int m1 = 0; m1 < 2; m1++)
			for (int m2 = 0; m2 < 2; m2++) {
				// cout << "@@ " << dp[n - 1][k][rev][m1][m2] << "\n";
				res = _sum(res, sum[n - 1][k][rev][m1][m2]);
				cnt = _sum(cnt, dp[n - 1][k][rev][m1][m2]);
			}

	res = _sum(res, _mul(cnt, _pow(2, n - 1)));
	return res;
}

int main() {
	cin >> n >> k;
	cin >> s >> c >> L >> c >> R;
	for (int i = 0; i < n - 1; i++)
		s[i] = '0' + (s[i] == 'R');

	cout << calc(s, L, R) << "\n";
	return 0;
}

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