QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127577 | #6325. Peaceful Results | Energy_is_not_over | RE | 123ms | 28848kb | C++17 | 7.2kb | 2023-07-19 19:59:11 | 2023-07-19 19:59:14 |
Judging History
answer
/**
* created: 17/07/2023, 20:21:09
**/
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int max_n = 1500111, mod = 998244353;
template<int mod>
struct NTT {
static constexpr int max_lev = __builtin_ctz(mod - 1);
int prod[2][max_lev - 1];
NTT() {
int root = (mod == 998244353) ? 31 : find_root();
int rroot = inv(root);
vector<vector<int>> roots(2, vector<int>(max_lev - 1));
roots[0][max_lev - 2] = root;
roots[1][max_lev - 2] = rroot;
for (int tp = 0; tp < 2; ++tp) {
for (int i = max_lev - 3; i >= 0; --i) {
roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
}
}
for (int tp = 0; tp < 2; ++tp) {
int cur = 1;
for (int i = 0; i < max_lev - 1; ++i) {
prod[tp][i] = mul(cur, roots[tp][i]);
cur = mul(cur, roots[tp ^ 1][i]);
}
}
}
template<bool inverse>
void fft(int *a, int lg) const {
const int n = 1 << lg;
int pos = max_lev - 1;
for (int it = 0; it < lg; ++it) {
const int h = inverse ? lg - 1 - it : it;
const int shift = (1 << (lg - h - 1));
int coef = 1;
for (int start = 0; start < (1 << h); ++start) {
for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
if (!inverse) {
const int y = mul(a[i + shift], coef);
a[i + shift] = a[i];
inc(a[i], y);
dec(a[i + shift], y);
} else {
const int y = mul(a[i] + mod - a[i + shift], coef);
inc(a[i], a[i + shift]);
a[i + shift] = y;
}
}
coef = mul(coef, prod[inverse][__builtin_ctz(~start)]);
}
}
if (inverse) {
const int rn = inv(n);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], rn);
}
}
}
vector<int> product(vector<int> a, vector<int> b) const {
if (a.empty() || b.empty()) {
return {};
}
const int sz = a.size() + b.size() - 1;
const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
a.resize(n);
b.resize(n);
fft<false>(a.data(), lg);
fft<false>(b.data(), lg);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], b[i]);
}
fft<true>(a.data(), lg);
a.resize(sz);
return a;
}
vector<int> square(vector<int> a) const {
if (a.empty()) {
return {};
}
const int sz = a.size() + a.size() - 1;
const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
a.resize(n);
fft<false>(a.data(), lg);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], a[i]);
}
fft<true>(a.data(), lg);
a.resize(sz);
return a;
}
static int find_root() {
for (int root = 2; ; ++root) {
if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
return root;
}
}
}
static inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
static inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
static inline int mul(int x, int y) {
return (1LL * x * y) % mod;
}
static int power(int x, int y) {
if (y == 0) {
return 1;
}
if (y % 2 == 0) {
return power(mul(x, x), y / 2);
}
return mul(x, power(x, y - 1));
}
static int inv(int x) {
return power(x, mod - 2);
}
};
NTT<mod> ntt;
inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
inline int mul(int x) {
return x;
}
template<typename... Args>
inline int mul(int x, Args... args) {
return (1LL * x * mul(args...)) % mod;
}
int power(int a, int b) {
int res = 1 % mod;
while (b) {
if (b % 2) {
res = mul(res, a);
}
b /= 2;
a = mul(a, a);
}
return res;
}
int inv(int x) {
return power(x, mod - 2);
}
string str_fraction(int x, int n = 20) {
stringstream res;
pair<int, int> best(x, 1);
for (int j = 1; j < n; ++j) {
best = min(best, {mul(x, j), j});
best = min(best, {mod - mul(x, j), -j});
}
if (best.second < 0) {
best.first *= -1;
best.second *= -1;
}
res << best.first << "/" << best.second;
return res.str();
}
const int max_f = 1500111;
int F[max_f], rf[max_f];
void get_all_f() {
F[0] = rf[0] = 1;
for (int i = 1; i < max_f; ++i) {
F[i] = mul(i, F[i - 1]);
}
rf[max_f - 1] = inv(F[max_f - 1]);
for (int i = max_f - 2; i > 0; --i) {
rf[i] = mul(i + 1, rf[i + 1]);
}
}
int get_c(int n, int k) {
if (n < k || k < 0) {
return 0;
}
return mul(F[n], mul(rf[k], rf[n - k]));
}
int get_c(int n, int k1, int k2) {
if (n < k1 + k2 || k1 < 0 || k2 < 0) {
return 0;
}
return mul(F[n], rf[k1], rf[k2], rf[n - k1 - k2]);
}
int n;
int a, b, c;
int d, e, f;
int g, h, i;
int solve() {
int res = 0;
const int k = g - b - e;
const int l = a + d - h;
const int m = i - f + a + b;
if ((m + l) % 3) {
return 0;
}
const int p = (m + l) / 3;
const int q = p - l;
vector<int> A(a + 1), B(a + 1);
for (int y = 0; y <= a; ++y) {
if (b - p - q + y < 0 || d - p + y < 0) {
continue;
}
A[y] = mul(rf[y], rf[b - p - q + y], rf[d - p + y]);
}
for (int y = 0; y <= a; ++y) {
if (p - a + y < 0 || e - q - a + y < 0) {
continue;
}
B[y] = mul(rf[y], rf[p - a + y], rf[e - q - a + y]);
}
vector<int> C = ntt.product(A, B);
for (int x = 0; x <= a; ++x) {
if (q + x < 0 || q + x > b || c - d + p - e + q + x < 0 || c - d + p - e + q + x > c) {
continue;
}
int coef = mul(F[a], F[b], F[c], rf[x], rf[q + x], rf[c - d + p - e + q + x]);
inc(res, mul(coef, C[a - x]));
}
res = mul(res, get_c(n, a, b));
return res;
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
get_all_f();
cin >> n;
cin >> a >> b >> c;
cin >> d >> e >> f;
cin >> g >> h >> i;
cout << solve() << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 15220kb
input:
2 2 0 0 1 1 0 1 0 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 12ms
memory: 15168kb
input:
3 0 1 2 3 0 0 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 33ms
memory: 18044kb
input:
333333 111111 111111 111111 111111 111111 111111 111111 111111 111111
output:
383902959
result:
ok 1 number(s): "383902959"
Test #4:
score: 0
Accepted
time: 123ms
memory: 28848kb
input:
1500000 500000 500000 500000 500000 500000 500000 500000 500000 500000
output:
355543262
result:
ok 1 number(s): "355543262"
Test #5:
score: 0
Accepted
time: 121ms
memory: 28780kb
input:
1499999 499999 499999 500001 499999 499999 500001 499999 499999 500001
output:
934301164
result:
ok 1 number(s): "934301164"
Test #6:
score: 0
Accepted
time: 16ms
memory: 15168kb
input:
1500000 1 0 1499999 1499999 1 0 0 1499999 1
output:
1500000
result:
ok 1 number(s): "1500000"
Test #7:
score: -100
Runtime Error
input:
1499999 0 749999 750000 750000 0 749999 749999 750000 0