QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48875#1242. Broken lineckiseki#ML 0ms0kbC++4.0kb2022-09-16 18:56:512022-09-16 18:56:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-16 18:56:54]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2022-09-16 18:56:51]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

banan

output:


result: