QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164362 | #1245. Three balls | ucup-team1600# | WA | 6ms | 4444kb | C++20 | 10.3kb | 2023-09-04 22:04:04 | 2023-09-04 22:04:05 |
Judging History
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'