#include <iostream> #include <algorithm> long long p = 1000000007; bool contains(int r1, int r2, int dist); long long capacity(int r, int dim); long long nOverK(int n, int k); long long intersection(int r1, int r2, int dist, int dim); long long sum(int r1, int r2, int dist, int dim); long long pow2(int n); long long int reciprocal(long long n); long long pow(long long a, unsigned long long b); long long int intersection123(int r1, int r2, int r3, int k1, int k2, int k3, int dim, long long defaultVal); int main() { //region input char arr[3][10000]; int n, r1, r2, r3; std::cin >> n; std::cin >> r1; for (int i = 0; i < n; ++i) { std::cin >> arr[0][i]; } std::cin >> r2; for (int i = 0; i < n; ++i) { std::cin >> arr[1][i]; } std::cin >> r3; for (int i = 0; i < n; ++i) { std::cin >> arr[2][i]; } int k0{}, k1{}, k2{}, k3{}; for (int i = 0; i < n; ++i) { k1 += (arr[1][i] == arr[2][i] and arr[0][i] != arr[1][i]); } for (int i = 0; i < n; ++i) { k2 += (arr[0][i] == arr[2][i] and arr[1][i] != arr[0][i]); } for (int i = 0; i < n; ++i) { k3 += (arr[0][i] == arr[1][i] and arr[2][i] != arr[1][i]); } k0 = n - k1 - k2 - k3; //endregion //region no common part if (r1 >= n or r2 >= n or r3 >= n) { std::cout << pow2(n); return 0; } if (contains(r1, r2, k1 + k2)) { std::cout << sum(r1, r3, k1 + k3, n); return 0; } if (contains(r2, r1, k2 + k1)) { std::cout << sum(r2, r3, k2 + k3, n); return 0; } if (contains(r1, r3, k1 + k3)) { std::cout << sum(r1, r2, k1 + k2, n); return 0; } if (contains(r3, r1, k3 + k1)) { std::cout << sum(r3, r2, k3 + k2, n); return 0; } if (contains(r2, r3, k2 + k3)) { std::cout << sum(r2, r1, k2 + k1, n); return 0; } if (contains(r3, r2, k3 + k2)) { std::cout << sum(r3, r1, k3 + k1, n); return 0; } // endregion long long c1 = capacity(r1, n); long long c2 = capacity(r2, n); long long c3 = capacity(r3, n); long long i12 = intersection(r1, r2, k1 + k2, n); long long i23 = intersection(r2, r3, k2 + k3, n); long long i31 = intersection(r3, r1, k3 + k1, n); if (i12 == 0 or i23 == 0 or i31 == 0) { long long res = c1 + c2 + c3 - i12 - i23 - i31; if (res < 0) res += p; std::cout << (res % p) << '\n'; return 0; } long long i123 = intersection123(r1, r2, r3, k1, k2, k3, n, std::min(std::min(i12, i23), i31)); long long res = c1 + c2 + c3 - i12 - i23 - i31 + i123; if (res < 0) res += p; std::cout << (res % p) << '\n'; } struct B { int r, k; [[nodiscard]] int d() const { return r - k; } }; long long intersection123(int r1, int r2, int r3, int k1, int k2, int k3, int dim, long long defaultValue) { B l[] = { B{r1, k1}, B{r2, k2}, B{r3, k3} }; std::sort(l, l + 3, [](const B &b1, const B&b2) { return b1.d() < b2.d(); }); if (l[0].d() == 0 and l[1].d() == 0) { long long result = 0; for (int i = 0; i < l[2].d() / 2; ++i) { result += nOverK(l[0].k, i) * nOverK(l[1].k, i); } return result % p; } if (l[0].d() == -l[1].d()) { long long result = 0; for (int i = 0; i < (l[2].d() - l[1].d()) / 2; ++i) { result += nOverK(l[0].k - l[1].d(), i) * nOverK(l[1].k - l[1].d(), i); result %= p; } result *= nOverK(l[0].k, l[1].d()); result %= p; return result; } if (l[0].d() < 0) { return 0; } else { return defaultValue; } } long long pow2(int n) { long long result = 1; for (int i = 0; i < n; ++i) { result *= 2; result %= p; } return result % p; } long long sum(int r1, int r2, int dist, int dim) { long long sum = capacity(r1, dim) + capacity(r2, dim) - intersection(r1, r2, dist, dim); if (sum < 0) sum += p; return sum % p; } long long intersection(int r1, int r2, int dist, int dim) { long long result = 0; int start = std::min(r1, dist); int end = std::max(dist - r2, 0); for (int i = start; i >= end; --i) { result += nOverK(dist, i) * nOverK(dim - dist, std::min(r1 - i, r2 - (dist - i))); } return result % p; } long long capacity(int r, int dim) { long long result = 0; for (int i = 0; i <= r; ++i) { result += nOverK(dim, i); } return result % p; } long long nOverK(int n, int k) { if (n < k) return 0; long long result = 1; for (int i = 0; i < k; ++i) { result *= n - i; result %= p; } long long divisor = 1; for (int i = 1; i <= k; ++i) { divisor *= i; divisor %= p; } auto rec = reciprocal(divisor); result *= rec; return result % p; } long long int reciprocal(long long n) { return pow(n, p - 2); } long long pow(long long a, unsigned long long b) { long long result = 1; long long tmp = a; while (b) { if (b & 1u) { result *= tmp; result %= p; } tmp *= tmp; tmp %= p; b >>= 1u; } return result; } bool contains(int r1, int r2, int dist) { return r1 >= r2 + dist; }
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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 | #include <iostream> #include <algorithm> long long p = 1000000007; bool contains(int r1, int r2, int dist); long long capacity(int r, int dim); long long nOverK(int n, int k); long long intersection(int r1, int r2, int dist, int dim); long long sum(int r1, int r2, int dist, int dim); long long pow2(int n); long long int reciprocal(long long n); long long pow(long long a, unsigned long long b); long long int intersection123(int r1, int r2, int r3, int k1, int k2, int k3, int dim, long long defaultVal); int main() { //region input char arr[3][10000]; int n, r1, r2, r3; std::cin >> n; std::cin >> r1; for (int i = 0; i < n; ++i) { std::cin >> arr[0][i]; } std::cin >> r2; for (int i = 0; i < n; ++i) { std::cin >> arr[1][i]; } std::cin >> r3; for (int i = 0; i < n; ++i) { std::cin >> arr[2][i]; } int k0{}, k1{}, k2{}, k3{}; for (int i = 0; i < n; ++i) { k1 += (arr[1][i] == arr[2][i] and arr[0][i] != arr[1][i]); } for (int i = 0; i < n; ++i) { k2 += (arr[0][i] == arr[2][i] and arr[1][i] != arr[0][i]); } for (int i = 0; i < n; ++i) { k3 += (arr[0][i] == arr[1][i] and arr[2][i] != arr[1][i]); } k0 = n - k1 - k2 - k3; //endregion //region no common part if (r1 >= n or r2 >= n or r3 >= n) { std::cout << pow2(n); return 0; } if (contains(r1, r2, k1 + k2)) { std::cout << sum(r1, r3, k1 + k3, n); return 0; } if (contains(r2, r1, k2 + k1)) { std::cout << sum(r2, r3, k2 + k3, n); return 0; } if (contains(r1, r3, k1 + k3)) { std::cout << sum(r1, r2, k1 + k2, n); return 0; } if (contains(r3, r1, k3 + k1)) { std::cout << sum(r3, r2, k3 + k2, n); return 0; } if (contains(r2, r3, k2 + k3)) { std::cout << sum(r2, r1, k2 + k1, n); return 0; } if (contains(r3, r2, k3 + k2)) { std::cout << sum(r3, r1, k3 + k1, n); return 0; } // endregion long long c1 = capacity(r1, n); long long c2 = capacity(r2, n); long long c3 = capacity(r3, n); long long i12 = intersection(r1, r2, k1 + k2, n); long long i23 = intersection(r2, r3, k2 + k3, n); long long i31 = intersection(r3, r1, k3 + k1, n); if (i12 == 0 or i23 == 0 or i31 == 0) { long long res = c1 + c2 + c3 - i12 - i23 - i31; if (res < 0) res += p; std::cout << (res % p) << '\n'; return 0; } long long i123 = intersection123(r1, r2, r3, k1, k2, k3, n, std::min(std::min(i12, i23), i31)); long long res = c1 + c2 + c3 - i12 - i23 - i31 + i123; if (res < 0) res += p; std::cout << (res % p) << '\n'; } struct B { int r, k; [[nodiscard]] int d() const { return r - k; } }; long long intersection123(int r1, int r2, int r3, int k1, int k2, int k3, int dim, long long defaultValue) { B l[] = { B{r1, k1}, B{r2, k2}, B{r3, k3} }; std::sort(l, l + 3, [](const B &b1, const B&b2) { return b1.d() < b2.d(); }); if (l[0].d() == 0 and l[1].d() == 0) { long long result = 0; for (int i = 0; i < l[2].d() / 2; ++i) { result += nOverK(l[0].k, i) * nOverK(l[1].k, i); } return result % p; } if (l[0].d() == -l[1].d()) { long long result = 0; for (int i = 0; i < (l[2].d() - l[1].d()) / 2; ++i) { result += nOverK(l[0].k - l[1].d(), i) * nOverK(l[1].k - l[1].d(), i); result %= p; } result *= nOverK(l[0].k, l[1].d()); result %= p; return result; } if (l[0].d() < 0) { return 0; } else { return defaultValue; } } long long pow2(int n) { long long result = 1; for (int i = 0; i < n; ++i) { result *= 2; result %= p; } return result % p; } long long sum(int r1, int r2, int dist, int dim) { long long sum = capacity(r1, dim) + capacity(r2, dim) - intersection(r1, r2, dist, dim); if (sum < 0) sum += p; return sum % p; } long long intersection(int r1, int r2, int dist, int dim) { long long result = 0; int start = std::min(r1, dist); int end = std::max(dist - r2, 0); for (int i = start; i >= end; --i) { result += nOverK(dist, i) * nOverK(dim - dist, std::min(r1 - i, r2 - (dist - i))); } return result % p; } long long capacity(int r, int dim) { long long result = 0; for (int i = 0; i <= r; ++i) { result += nOverK(dim, i); } return result % p; } long long nOverK(int n, int k) { if (n < k) return 0; long long result = 1; for (int i = 0; i < k; ++i) { result *= n - i; result %= p; } long long divisor = 1; for (int i = 1; i <= k; ++i) { divisor *= i; divisor %= p; } auto rec = reciprocal(divisor); result *= rec; return result % p; } long long int reciprocal(long long n) { return pow(n, p - 2); } long long pow(long long a, unsigned long long b) { long long result = 1; long long tmp = a; while (b) { if (b & 1u) { result *= tmp; result %= p; } tmp *= tmp; tmp %= p; b >>= 1u; } return result; } bool contains(int r1, int r2, int dist) { return r1 >= r2 + dist; } |