QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164362#1245. Three ballsucup-team1600#WA 6ms4444kbC++2010.3kb2023-09-04 22:04:042023-09-04 22:04:05

Judging History

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

  • [2023-09-04 22:04:05]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:4444kb
  • [2023-09-04 22:04:04]
  • 提交

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

const int debug = 0;

mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}


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

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

    m1:
    int n;
    if (!debug) {
        cin >> n;
    }
    else {
        n = randll(1, 3);
    }
    inv_fact(n + 5);
    vector <pair<int, string> > a(3);
    mint ans = 0;
    for (auto &i : a) {
        if (!debug) {
            cin >> i.first >> i.second;
        }
        else {
            i.first = randll(0, n);
            for (int j = 0; j < n; j++) {
                i.second += "01"[randll(0, 1)];
            }
        }
        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];
    };
    LOG(ans, "start");
    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 = min({(R - L + 2) / 2, c[3] - L + 1, R + 1});
                LOG(coeff);
                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;
//                int to = L - 1 + cnt;
//                if (to > c[3]) {
//                    ans -= pref.back() * get_pref(cnt - (to - c[3] - 1), cnt) * coeff;
//                }
                LOG("end", ans);
            }
        }
    }
    LOG(ans);
    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';
    if (debug) {
        int res = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int h[3] = {};
            for (int j = 0; j < n; j++) {
                char cur = '0' + bool(mask & (1 << j));
                if (cur != a[0].second[j]) ++h[0];
                if (cur != a[1].second[j]) ++h[1];
                if (cur != a[2].second[j]) ++h[2];
            }
            if (h[0] <= a[0].first || h[1] <= a[1].first || h[2] <= a[2].first) {
                ++res;
            }
        }
        LOG(ans, res);
        if (ans != res) {
            LOG(n);
            for (int i = 0; i < 3; i++) {
                LOG(a[i].first, a[i].second);
            }
        }
        assert(ans == res);
        goto m1;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3892kb

input:

3
1 000
1 100
0 111

output:

7

result:

ok answer is '7'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

5
2 10110
0 11010
1 00000

output:

19

result:

ok answer is '19'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

3
2 011
0 100
3 010

output:

8

result:

ok answer is '8'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

5
1 11010
3 00001
4 01011

output:

32

result:

ok answer is '32'

Test #5:

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

input:

1
1 1
1 1
1 0

output:

2

result:

ok answer is '2'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3920kb

input:

1
1 0
0 1
1 0

output:

2

result:

ok answer is '2'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

10
4 0001001011
6 0000011100
4 1011000101

output:

969

result:

ok answer is '969'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

15
4 110001100010010
11 101101011011001
0 001110001001110

output:

32227

result:

ok answer is '32227'

Test #9:

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

input:

15
9 011001010111000
7 101000010111010
9 010000110010010

output:

31656

result:

ok answer is '31656'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

15
15 011010001011011
6 101000010001001
6 000010111110010

output:

32768

result:

ok answer is '32768'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

15
0 100010010001000
0 011100000001011
0 100000100111111

output:

3

result:

ok answer is '3'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3932kb

input:

14
0 11101010011000
0 11101010011000
0 11101010011000

output:

1

result:

ok answer is '1'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

37
28 1001101111100111110011111100101110110
32 1001011110011111110100111110100110010
21 1001000111000000110011000001100011111

output:

438952513

result:

ok answer is '438952513'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

37
21 0101010101010101010101010101010101010
20 0011001100110011001100110011001100110
22 0000111100001111000011110000111100001

output:

16781879

result:

ok answer is '16781879'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

36
14 001110110001000000000111001011111101
13 100000010110111010011100111111010100
12 011111111010110111110010110011100100

output:

765072297

result:

ok answer is '765072297'

Test #16:

score: -100
Wrong Answer
time: 6ms
memory: 4444kb

input:

1500
653 101110010010011101100010011000000111010100100001101000000010010011001011101111100111100101000111001110000011111110011010101011111101001011011001100010100100101100100101000010001101011111100001010000101000100110110001011011001111100001010110101000000111010111001011110011110100110101111111110...

output:

978439397

result:

wrong answer expected '979972096', found '978439397'