Loj 3223 Trzy kule

Posted on | Views:

Meet in the middle + 二维前缀和.

首先可以补集转化一下,用 $2^n$ 减掉三个不等式都不成立的方案数.

将每个 $r$ 变为 $n-1-r$ ,则我们需要求出与每个串相同的字符数都不超过对应的 $r$ 的方案数.

首先可以将这三个串都异或上第一个串,答案不变,于是一个位置只会有 $000,001,010,011$ 这四种情况.

记串 $S$ 中,这四种位置上 $0$ 的数目分别为 $c_0,c_1,c_2,c_3$ .

考虑 Meet in the middle, 先枚举 $c_0,c_1$ ,再枚举 $c_2,c_3$ ,询问能凑成合法四元组的 $c_0,c_1$ 的贡献总和.

看上去有 3 个维度的限制,但是 $c_0,c_1$ 对应的点中有 2 维是一样的,于是可以缩成 2 维,变成单点加,最后矩形求和.

由于每个维度的坐标都不会超过 $2n$ ,所以直接用二维前缀和处理即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 2e4 + 10;
int n, r[3], s[N][N], k[4], c[4], fac[N], invfac[N];
char buf[3][N];
int binom(int x, int y)
{
	return mul(fac[x], mul(invfac[y], invfac[x - y]));
}
int main()
{
	n = read();
	for (int i = 0; i < 3; ++i)
	{
		r[i] = n - 1 - read();
		if (r[i] < 0)
			return write(fpow(2, n), '\n'), 0;
		scanf("%s", buf[i] + 1);
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		fac[i] = mul(fac[i - 1], i);
		int x = buf[0][i] - '0', y = buf[1][i] - '0', z = buf[2][i] - '0';
		y ^= x, z ^= x;
		k[y << 1 | z]++;
	}
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	int w = 0, h = 0;
	for (c[0] = 0; c[0] <= k[0]; ++c[0])
	{
		int t = binom(k[0], c[0]);
		for (c[1] = 0; c[1] <= k[1]; ++c[1])
		{
			int x = c[0] + c[1];
			int y = k[1] + c[0] - c[1];
			w = max(w, x), h = max(h, y);
			inc(s[x][y], mul(t, binom(k[1], c[1])));
		}
	}
	for (int i = 0; i <= w; ++i)
		for (int j = 0; j <= h; ++j)
		{
			if (i)
				inc(s[i][j], s[i - 1][j]);
			if (j)
				inc(s[i][j], s[i][j - 1]);
			if (i && j)
				inc(s[i][j], P - s[i - 1][j - 1]);
		}
	int ans = 0;
	for (c[2] = 0; c[2] <= k[2]; ++c[2])
	{
		int t = binom(k[2], c[2]);
		for (c[3] = 0; c[3] <= k[3]; ++c[3])
		{
			int x = min(r[0] - c[2] - c[3], r[1] + c[2] + c[3] - k[2] - k[3]);
			if (x < 0)
				continue;
			x = min(x, w);
			int y = r[2] - c[2] + c[3] - k[3];
			if (y < 0)
				continue;
			y = min(y, h);
			inc(ans, mul(mul(t, binom(k[3], c[3])), s[x][y]));
		}
	}
	ans = add(fpow(2, n), P - ans);
	write(ans, '\n');
	return 0;
}