QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#48875 | #1242. Broken line | ckiseki# | ML | 0ms | 0kb | C++ | 4.0kb | 2022-09-16 18:56:51 | 2022-09-16 18:56:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
static constexpr int mod = 1'000'000'007;
static constexpr int maxn = 10000 + 1;
static constexpr inline int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
static constexpr inline int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
static constexpr inline int mul(int64_t a, int64_t b) {
return static_cast<int>(a * b % mod);
}
static constexpr inline int qpow(int a, int64_t k) {
int r = 1;
while (k) {
if (k & 1) r = mul(r, a);
k >>= 1; a = mul(a, a);
}
return r;
}
int fac[maxn], ifac[maxn];
static inline int comb(int n, int k) {
return mul(fac[n], mul(ifac[k], ifac[n - k]));
}
int o[2][2];
int s[maxn][maxn];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
fac[0] = 1;
for (int i = 1; i < maxn; ++i)
fac[i] = mul(fac[i - 1], i);
ifac[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 0; --i)
ifac[i] = mul(ifac[i + 1], i + 1);
int n; cin >> n;
int X, Y, Z;
string s1, s2, s3;
cin >> X >> s1;
cin >> Y >> s2;
cin >> Z >> s3;
for (int i = 0; i < n; ++i) {
o[s1[i] != s2[i]][s1[i] != s3[i]]++;
}
const int A = o[0][0], B = o[0][1], C = o[1][0], D = o[1][1];
//cout << A << ", " << B << ", " << C << ", " << D << '\n';
int ans = qpow(2, n);
//for (int a = 0; a <= A; ++a) {
// for (int b = 0; b <= B; ++b) {
// for (int c = 0; c <= C; ++c) {
// for (int d = 0; d <= D; ++d) {
// if (a + b + c + d <= X) continue;
// if (a + b + (C - c) + (D - d) <= Y) continue;
// if (a + (B - b) + c + (D - d) <= Z) continue;
// cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
// ans = sub(ans, mul(mul(comb(A, a), comb(B, b)), mul(comb(C, c), comb(D, d))));
// }
// }
// }
//}
for (int c = 0; c <= C; ++c) {
for (int d = 0; d <= D; ++d) {
if (c - d <= 0) break;
s[c - d][c + d] = add(s[c - d][c + d], mul(comb(C, c), comb(D, d)));
}
}
for (int i = 0; i < maxn; ++i) {
for (int j = 1; j < maxn; ++j)
s[i][j] = add(s[i][j], s[i][j - 1]);
}
for (int i = maxn - 2; i >= 0; --i) {
for (int j = 0; j < maxn; ++j)
s[i][j] = add(s[i][j], s[i + 1][j]);
}
for (int a = 0; a <= A; ++a) {
for (int b = 0; b <= B; ++b) {
int lhs = X - a - b;
int rhs = a + b + C + D - Y;
int suf = max(-1, Z - a - (B - b) - D);
if (suf + 1 >= maxn) continue;
rhs = min(rhs, maxn);
lhs = max(lhs, -1);
if (lhs >= rhs - 1) continue;
int tot = lhs < 0 ? s[suf + 1][rhs - 1] : sub(s[suf + 1][rhs - 1], s[suf + 1][lhs]);
ans = sub(ans, mul(mul(comb(A, a), comb(B, b)), tot));
}
}
memset(s, 0, sizeof(s));
for (int c = 0; c <= C; ++c) {
for (int d = c; d <= D; ++d) {
s[d - c][c + d] = add(s[d - c][c + d], mul(comb(C, c), comb(D, d)));
}
}
for (int i = 0; i < maxn; ++i) {
for (int j = 1; j < maxn; ++j)
s[i][j] = add(s[i][j], s[i][j - 1]);
}
for (int i = 1; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j)
s[i][j] = add(s[i][j], s[i - 1][j]);
}
for (int a = 0; a <= A; ++a) {
for (int b = 0; b <= B; ++b) {
int lhs = X - a - b;
int rhs = a + b + C + D - Y;
int suf = a + (B - b) + D - Z;
suf = min(suf, maxn);
if (suf - 1 < 0) continue;
rhs = min(rhs, maxn);
lhs = max(lhs, -1);
if (lhs >= rhs - 1) continue;
int tot = lhs < 0 ? s[suf - 1][rhs - 1] : sub(s[suf - 1][rhs - 1], s[suf + 1][lhs]);
ans = sub(ans, mul(mul(comb(A, a), comb(B, b)), tot));
}
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
banan