QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91114 | #4903. 细菌 | HgCl2 | 15 | 332ms | 63096kb | C++14 | 5.2kb | 2023-03-27 12:57:23 | 2023-03-27 12:57:37 |
Judging History
answer
#include <bits/stdc++.h>
template <typename T, size_t ...sizes>
struct NestedArray {};
template <typename T, size_t size, size_t ...sizes>
struct NestedArray<T, size, sizes...> {
using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};
template <typename T>
struct NestedArray<T> {
using Type = T;
};
template <typename T, size_t ...sizes>
using Array = typename NestedArray<T, sizes...>::Type;
void OptimizeIO() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
}
void OptimizeIO(const std::string &input_file, const std::string &output_file) {
static std::ifstream input_stream(input_file);
static std::ofstream output_stream(output_file);
std::cin.rdbuf(input_stream.rdbuf());
std::cout.rdbuf(output_stream.rdbuf());
std::cin.tie(nullptr), std::cout.tie(nullptr);
}
const int kMaxN = 1 << 19;
const int kMaxD = 1.2e5 + 5, kMax18D = kMaxD * 18;
const int kMod = 998244353, kG = 3;
const int kInv2 = (kMod + 1) / 2, kInvG = (kMod + 1) / 3;
int d, n, m, k, a, b, c, q, block_len, lim;
Array<int, kMaxD> fac, inv_fac;
Array<int, kMaxN> rev, f, g, h;
struct Query {
int n, m, type, coef, pos, block_n;
Query(): n(0), m(0), type(0), coef(0), pos(0), block_n(0) {}
Query(int n, int m, int type, int coef, int pos):
n(n), m(m), type(type), coef(coef), pos(pos) {
block_n = (n - 1) / block_len + 1;
}
};
inline bool operator<(const Query &a, const Query &b) {
if (a.block_n != b.block_n) return a.block_n < b.block_n;
return (a.block_n & 1 ? a.m < b.m : a.m > b.m);
}
Array<Query, kMax18D> query;
inline void Add(int &a, int b) {
a += b;
if (a >= kMod) a -= kMod;
}
inline int Sum(int a, int b) {
a += b;
if (a >= kMod) a -= kMod;
return a;
}
inline void Sub(int &a, int b) {
a -= b;
if (a < 0) a += kMod;
}
inline int Dif(int a, int b) {
a -= b;
if (a < 0) a += kMod;
return a;
}
inline int Unm(int a) { return a ? kMod - a : a; }
inline void Mul(int &a, int b) {
a = static_cast<int64_t>(a) * b % kMod;
}
inline int Prod(int a, int b) {
return static_cast<int64_t>(a) * b % kMod;
}
inline int Prod(std::initializer_list<int> list) {
return std::accumulate(list.begin(), list.end(), static_cast<int64_t>(1),
[](int64_t prod, int x) { return prod * x % kMod; });
}
int Pow(int a, int b) {
int ans = 1, prod = a;
while (b) {
if (b & 1) Mul(ans, prod);
Mul(prod, prod), b >>= 1;
}
return ans;
}
inline int Inv(int a) {
return Pow(a, kMod - 2);
}
void Init() {
fac[0] = 1;
for (int i = 1; i <= d; i++) fac[i] = Prod(fac[i - 1], i);
inv_fac[d] = Inv(fac[d]);
for (int i = d; i >= 1; i--) inv_fac[i - 1] = Prod(inv_fac[i], i);
}
inline int Choose(int n, int m) {
if (n < m) return 0;
return Prod({fac[n], inv_fac[m], inv_fac[n - m]});
}
inline void F(int a, int b, int d, int type, int coef) {
if (b < 0) return;
query[++q] = Query(d, std::min(b, d), type, coef, d);
if (a > 0) query[++q] = Query(d, a - 1, type, Unm(coef), d);
}
inline void F(int a, int b, int x, int d, int type, int coef) {
F(((d - a + 1) >> 1) + x, ((d + b) >> 1) + x, d, type, coef);
}
inline void G(int a, int b, int d, int type) {
F(a, b, 0, d, type, inv_fac[d]);
F(a, b, a + 1, d, type, Unm(inv_fac[d]));
F(a, b, -b - 1, d, type, Unm(inv_fac[d]));
}
void GetEgf(int a, int b, int type) {
for (int i = 0; i <= d; i++) G(a, b, i, type);
}
void AnswerQuery() {
std::sort(query.begin() + 1, query.begin() + q + 1);
int n = 0, m = 0, sum = 1;
for (int i = 1; i <= q; i++) {
while (n > query[i].n) sum = Prod(Sum(sum, Choose(n - 1, m)), kInv2), n--;
while (n < query[i].n) sum = Dif(Sum(sum, sum), Choose(n, m)), n++;
while (m < query[i].m) Add(sum, Choose(n, ++m));
while (m > query[i].m) Sub(sum, Choose(n, m--));
int val = Prod(sum, query[i].coef);
Add((query[i].type == 1 ? f : query[i].type == 2 ? g : h)[query[i].pos], val);
}
}
void GetRev() {
for (int i = 0; i < (1 << lim); i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
}
}
void Ntt(Array<int, kMaxN> &f, int type) {
for (int i = 0; i < (1 << lim); i++) {
if (i < rev[i]) std::swap(f[i], f[rev[i]]);
}
for (int i = 1; i < (1 << lim); i <<= 1) {
int w_n = Pow(type == 1 ? kG : kInvG, (kMod - 1) / (i << 1));
for (int j = 0; j < (1 << lim); j += (i << 1)) {
int w_n_k = 1;
for (int k = 0; k < i; k++) {
int x = f[j | k], y = Prod(f[i | j | k], w_n_k);
f[j | k] = Sum(x, y), f[i | j | k] = Dif(x, y);
Mul(w_n_k, w_n);
}
}
}
if (type == -1) {
int inv_n = Inv(1 << lim);
for (int i = 0; i < (1 << lim); i++) Mul(f[i], inv_n);
}
}
int main() {
OptimizeIO();
std::cin >> d >> n >> m >> k >> a >> b >> c;
n--, m--, k--, a--, b--, c--;
Init();
block_len = std::sqrt(n);
GetEgf(a, n - a, 1);
GetEgf(b, m - b, 2);
GetEgf(c, k - c, 3);
AnswerQuery();
while ((1 << lim) <= d * 3) lim++;
GetRev();
Ntt(f, 1);
Ntt(g, 1);
Ntt(h, 1);
for (int i = 0; i < (1 << lim); i++) Mul(f[i], Prod(g[i], h[i]));
Ntt(f, -1);
std::cout << Prod(f[d], fac[d]) << "\n";
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 53996kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 3ms
memory: 53948kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 16ms
memory: 54356kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 0
Accepted
time: 7ms
memory: 54328kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 310ms
memory: 63096kb
input:
120000 300 1 1 141 1 1
output:
765131153
result:
wrong answer 1st numbers differ - expected: '637174', found: '765131153'
Subtask #4:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 332ms
memory: 63040kb
input:
119000 119991 119991 1 23819 52139 1
output:
261942978
result:
wrong answer 1st numbers differ - expected: '944500934', found: '261942978'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%