QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164300#1245. Three ballsucup-team1600#WA 1ms3924kbC++208.7kb2023-09-04 21:24:112023-09-04 21:24:11

Judging History

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

  • [2023-09-04 21:24:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3924kb
  • [2023-09-04 21:24:11]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;

const int MOD = 1e9 + 7;
struct mint {
    int val;

    mint () : val(0) {}
    mint (int x) {
        if (-MOD <= x && x < MOD) {
            val = x;
        }
        else {
            val = x % MOD;
        }
        if (val < 0) val += MOD;
    }

    mint (ll x) {
        if (-MOD <= x && x < MOD) {
            val = x;
        }
        else {
            val = x % MOD;
        }
        if (val < 0) val += MOD;
    }

    mint (const mint& x) : val(x.val) {}

    constexpr mint& operator = (const mint& x) {
        val = x.val;
        return *this;
    }

    inline mint& operator += (const mint &x) {
        val += x.val;
        if (val >= MOD) {
            val -= MOD;
        }
        return *this;
    }

    inline mint& operator -= (const mint &x) {
        val -= x.val;
        if (val < 0) {
            val += MOD;
        }
        return *this;
    }

    inline mint operator - () const {
        mint tmp(*this);
        if (tmp.val) tmp.val = MOD - tmp.val;
        return tmp;
    }

    inline mint operator + (const mint &x) const {
        return mint(*this) += x;
    }

    inline mint operator - (const mint &x) const {
        return mint(*this) -= x;
    }

    inline mint& operator *= (const mint &x) {
        val = ((ll)val * x.val) % MOD;
        return *this;
    }

    inline mint operator * (const mint &x) const {
        return mint(*this) *= x;
    }

    inline mint binpow (int n) const {
        mint res = 1, tmp = *this;
        for (; n; n >>= 1) {
            if (n & 1) {
                res *= tmp;
            }
            tmp *= tmp;
        }
        return res;
    }

    inline mint inverse () const {
        return binpow(MOD - 2);
    }

    inline mint& operator /= (const mint &x) {
        return *this *= x.inverse();
    }

    inline mint operator / (const mint &x) {
        return mint(*this) *= x.inverse();
    }


    friend ostream& operator << (ostream &os, const mint &x) {
        os << x.val;
        return os;
    }

    friend istream& operator >> (istream &is, mint &x) {
        is >> x.val;
        return is;
    }

    inline bool operator == (const mint &x) const {
        return val == x.val;
    }

    inline bool operator != (const mint &x) const {
        return val != x.val;
    }

    inline bool operator < (const mint &x) const {
        return val < x.val;
    }

    inline bool operator > (const mint &x) const {
        return val > x.val;
    }

    friend string to_string (const mint &x) {
        return to_string(x.val);
    }

};

vector <mint> f = {1}, fi = {1};

inline mint fact (int n) {
    f.reserve(n + 1);
    while (len(f) <= n) {
        f.emplace_back(f.back() * len(f));
    }
    return f[n];
}

inline mint inv_fact (int n) { /// think
    if (len(fi) <= n) {
        fi.resize(n + 1, 0);
        mint val = mint(1) / fact(n);
        for (int i = n; fi[i] == 0; i--) {
            fi[i] = val;
            val *= i;
        }
    }
    return fi[n];
}

inline mint A (int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact(n) * inv_fact(n - k);
}

inline mint C (int n, int k) {
    if (k < 0 || k > n) return 0;
    return A(n, k) * inv_fact(k);
}


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    inv_fact(n + 5);
    vector <pair<int, string> > a(3);
    mint ans = 0;
    for (auto &i : a) {
        cin >> i.first >> i.second;
        for (int j = 0; j <= i.first; j++) {
            ans += C(n, j);
        }
    }
    int cc[8] = {};
    for (int i = 0; i < n; i++) {
        int mask = (a[0].second[i] - '0') | ((a[1].second[i] - '0') << 1) | ((a[2].second[i] - '0') << 2);
        int cnt = __builtin_popcount(mask);
        if (cnt > 1) {
            mask ^= 7;
        }
        ++cc[mask];
    }
    int c[4] = {cc[0], cc[1], cc[2], cc[4]};
    int r[4] = {0, a[0].first, a[1].first, a[2].first};

    vector <vector <mint> > pref1(c[3] + 1, vector <mint> (c[0] + 1));
    vector <vector <mint> > pref2(c[3] + 1, vector <mint> (c[0] + 1));

    vector <mint> pref(c[3] + 1);
    for (int i = 0; i <= c[3]; i++) {
        pref[i] = C(c[3], i);
        if (i) {
            pref[i] += pref[i - 1];
        }
    }


    for (int R = c[0]; R >= 0; R--) {
        for (int rr = 0; rr <= c[3]; rr++) {
            pref1[rr][R] = C(c[0], R) * pref[rr];
            if (rr && R + 1 <= c[0]) {
                pref1[rr][R] += pref1[rr - 1][R + 1];
            }
        }
    }

    for (int R = c[0]; R >= 0; R--) {
        for (int rr = 0; rr <= c[3]; rr++) {
            pref2[rr][R] = C(c[0], R) * pref[rr];
            if (rr + 1 <= c[3] && R + 1 <= c[0]) {
                pref2[rr][R] += pref2[rr + 1][R + 1];
            }
        }
    }

    vector <mint> PREF(c[0] + 1);
    for (int i = 0; i <= c[0]; i++) {
        PREF[i] = C(c[0], i);
        if (i) {
            PREF[i] += PREF[i - 1];
        }
    }


    auto get_pref = [&] (int l, int r) -> mint {
        umin(r, c[0]);
        umax(l, 0);
        if (l > r) {
            return 0;
        }
        return PREF[r] - (l ? PREF[l - 1] : mint(0));
    };

    auto get_sum1 = [&] (int r, int R) -> mint {
        mint res = 0;
        if (r > c[3]) {
            int diff = r - c[3];
            r -= diff;
            res = pref.back() * get_pref(R, R + diff - 1);
            R += diff;
        }
        if (r < 0 || R > c[0]) {
            return res;
        }
        return pref1[r][R] + res;
    };

    auto get_sum2 = [&] (int l, int R) -> mint {
        if (l < 0) {
            int diff = -l;
            l += diff;
            R += diff;
        }
        if (l > c[3] || R > c[0]) {
            return 0;
        }
        return pref2[l][R];
    };

    for (int x = 0; x <= c[1]; x++) {
        for (int y = 0; y <= c[2]; y++) {
            int L = max(x - y + c[2] + c[3] - r[1], y - x + c[1] + c[3] - r[2]);
            int R = r[3] - c[1] - c[2] + x + y;
            if (L <= R && R >= 0) {
                mint coeff = C(c[1], x) * C(c[2], y);
                int cnt = (R - L + 2) / 2;
//                LOG(L, R, cnt);
                ans += (get_sum1(R, 0) - get_sum1(R - cnt, cnt)) * coeff;
//                LOG(ans, get_sum1(R, 0));
                ans -= (get_sum2(L - 1, 0) - get_sum2(L - 1 + cnt, cnt)) * coeff;
            }
        }
    }
    auto solve = [&] (int A, int B) {
        int have[2] = {};
        for (int i = 0; i < n; i++) {
            ++have[a[A].second[i] != a[B].second[i]];
        }
        for (int x = 0; x <= have[0]; x++) {
            for (int y = 0; y <= have[1]; y++) {
                if (x + y <= a[A].first && x + have[1] - y <= a[B].first) {
                    ans -= C(have[0], x) * C(have[1], y);
                }
            }
        }
    };
    solve(0, 1);
    solve(0, 2);
    solve(1, 2);
    cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

input:

3
1 000
1 100
0 111

output:

7

result:

ok answer is '7'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

5
2 10110
0 11010
1 00000

output:

19

result:

ok answer is '19'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3688kb

input:

3
2 011
0 100
3 010

output:

9

result:

wrong answer expected '8', found '9'