QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#867084 | #9777. Balance in All Things | nhuang685 | AC ✓ | 4848ms | 732044kb | C++23 | 9.1kb | 2025-01-23 03:58:34 | 2025-01-23 03:58:34 |
Judging History
answer
/**
* @author n685
* @date 2025-01-21 16:50:08
*/
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
namespace rs = std::ranges;
namespace rv = std::views;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
namespace modular {
// from tourist
template <std::integral T> T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a;
std::swap(a, m);
u -= t * v;
std::swap(u, v);
}
assert(m == 1);
return u;
}
template <class Md, class V = long long>
requires std::signed_integral<std::decay_t<decltype(Md::value)>>
struct Mod {
using T = std::decay_t<decltype(Md::value)>;
T val = 0;
static constexpr T normalize(std::integral auto val) {
using U = decltype(Md::value + val);
U uval = static_cast<U>(val);
U umd = static_cast<U>(Md::value);
if (uval <= -umd || umd <= uval) {
uval %= umd;
}
if (val < 0) {
uval += umd;
}
return static_cast<T>(uval);
}
constexpr Mod() : val(0) {}
constexpr explicit Mod(std::integral auto _val) : val(normalize(_val)) {}
// addition
constexpr Mod& operator+=(Mod b) {
val += b.val;
if (val >= Md::value) {
val -= Md::value;
}
return *this;
}
friend constexpr Mod operator+(Mod a, Mod b) { return a += b; }
constexpr Mod& operator++() { return *this += Mod{1}; }
constexpr Mod operator++(int) {
Mod res = *this;
++(*this);
return res;
}
// subtraction
constexpr Mod& operator-=(Mod b) {
val -= b.val;
if (val < 0) {
val += Md::value;
}
return *this;
}
friend constexpr Mod operator-(Mod a, Mod b) { return a -= b; }
constexpr Mod& operator--() { return *this -= Mod{1}; }
constexpr Mod operator--(int) {
Mod res = *this;
--(*this);
return res;
}
// negation
constexpr Mod operator-() const { return Mod{-val}; }
// multiplication
constexpr Mod& operator*=(Mod b) {
val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
return *this;
}
friend constexpr Mod operator*(Mod a, Mod b) { return a *= b; }
constexpr Mod binpow(std::integral auto b) const {
Mod res{1}, a = *this;
while (b > 0) {
if (b % 2 == 1) {
res *= a;
}
a *= a;
b /= 2;
}
return res;
}
// factorial
// align with fft, if code fails to compile make this smaller (if using array)
static constexpr int MXINV = 1 << 22;
static inline bool init = false;
static inline std::vector<Mod> ff, iff;
static void reset_fac() { init = false; }
static void init_fac() {
if (init) {
return;
}
ff.resize(MXINV + 1);
ff[0] = Mod{1};
for (int i = 1; i <= MXINV; ++i) {
ff[i] = ff[i - 1] * Mod{i};
}
iff.resize(MXINV + 1);
iff[MXINV] = ff[MXINV].large_inv();
for (int i = MXINV - 1; i >= 0; --i) {
iff[i] = iff[i + 1] * Mod{i + 1};
}
init = true;
}
static Mod fac(int v) {
if (!init) {
init_fac();
}
return ff[v];
}
static Mod ifac(int v) {
if (!init) {
init_fac();
}
return iff[v];
}
static Mod comb(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return Mod{0};
}
return fac(n) * ifac(n - k) * ifac(k);
}
static Mod perm(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return Mod{0};
}
return fac(n) * ifac(n - k);
}
// inverse
Mod small_inv() const {
return ifac(static_cast<int>(val)) * fac(static_cast<int>(val) - 1);
}
constexpr Mod large_inv() const {
return Mod{inverse(val, Md::value)};
// return binpow(Md::value - 2);
}
Mod inv() const {
if (val <= MXINV) {
return small_inv();
}
return large_inv();
}
// sqrt
std::optional<Mod> sqrt() {
static std::mt19937_64 rng(
std::chrono::steady_clock::now().time_since_epoch().count());
Mod c{0};
while ((c * c - *this).binpow((Md::value - 1) / 2) == Mod{1}) {
c = Mod{rng()};
}
if (c == Mod{0}) {
return std::nullopt;
}
std::pair<Mod, Mod> res(Mod{1}, Mod{0}), a(c, Mod{1});
T b = (Md::value + 1) / 2;
auto mul = [&c, this](const std::pair<Mod, Mod>& u,
const std::pair<Mod, Mod>& v) -> std::pair<Mod, Mod> {
return {u.first * v.first + u.second * v.second * (c * c - *this),
u.second * v.first + u.first * v.second};
};
while (b > 0) {
if (b % 2 == 1) {
res = mul(res, a);
}
a = mul(a, a);
b /= 2;
}
return res.first;
// return std::min(res.first, -res.first);
}
// comparison
constexpr bool operator==(const Mod& b) const = default;
constexpr std::strong_ordering operator<=>(const Mod& b) const = default;
// io
friend std::istream& operator>>(std::istream& in, Mod& a) {
long long v;
in >> v;
a = Mod{v};
return in;
}
friend std::ostream& operator<<(std::ostream& out, const Mod& a) {
out << a.val;
return out;
}
// conversion
constexpr T value() const { return val; }
};
} // namespace modular
#if defined(LOCAL) && __cplusplus >= 202302L
template <class Md, class V>
requires std::formattable<typename modular::Mod<Md, V>::T, char>
struct std::formatter<modular::Mod<Md, V>, char> {
using T = typename modular::Mod<Md, V>::T;
std::formatter<T, char> underlying;
constexpr formatter() {
if constexpr (requires { underlying.set_debug_format(); }) {
underlying.set_debug_format();
}
}
template <class ParseContext> constexpr auto parse(ParseContext& ctx) {
return underlying.parse(ctx);
}
template <class FormatContext>
auto format(const modular::Mod<Md, V>& val, FormatContext& ctx) const {
return underlying.format(val.value(), ctx);
}
};
#endif
struct Md {
static inline int value;
};
using Mint = modular::Mod<Md>;
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int n, k;
std::cin >> n >> k >> Md::value;
std::vector<std::vector<std::vector<Mint>>> f(2 * n + 1);
f[0].resize(2 * n + 1);
for (int b = 0; b <= 2 * n; ++b) {
f[0][b].resize((2 * n - b) + 1);
if (b + b <= 2 * n) {
f[0][b][b] = Mint::fac(b);
}
}
for (int a = 1; a <= 2 * n; ++a) {
f[a].resize((2 * n - a) + 1);
for (int b = 0; a + b <= 2 * n; ++b) {
f[a][b].resize((2 * n - a - b) + 1);
for (int c = 0; a + b + c <= 2 * n; ++c) {
if (a >= 2) {
f[a][b][c] += Mint{a - 1} * f[a - 2][b][c];
}
if (b >= 1) {
f[a][b][c] += Mint{b} * f[a - 1][b - 1][c];
}
if (c >= 1) {
f[a][b][c] += Mint{c} * f[a - 1][b][c - 1];
}
}
}
}
std::vector<std::vector<std::vector<Mint>>> g(2 * n + 1);
// for convenience
g[0].resize(2 * n + 1);
for (int b = 0; b <= 2 * n; ++b) {
g[0][b].resize(b / 2 + 1);
g[0][b][0] = Mint{1};
}
for (int a = 1; a <= 2 * n; ++a) {
g[a].resize((2 * n - a) + 1);
for (int b = 0; (a + b) <= 2 * n; ++b) {
g[a][b].resize((a + b) / 2 + 1);
g[a][b][0] = Mint{1};
for (int c = 1; c <= (a + b) / 2; ++c) {
if (((a - 1) + b) / 2 >= c) {
g[a][b][c] = g[a - 1][b][c];
}
if (a >= 2) {
g[a][b][c] += Mint{a - 1} * g[a - 2][b][c - 1];
}
if (b >= 1) {
g[a][b][c] += Mint{b} * g[a - 1][b - 1][c - 1];
}
}
}
}
std::vector<Mint> h(2 * n + 1);
h[0] = Mint{1};
for (int i = 2; i <= 2 * n; i += 2) {
h[i] = Mint{i - 1} * h[i - 2];
}
dbg(h);
std::vector<Mint> even(n + 1);
std::vector odd(n + 1, std::vector<Mint>(n + 1));
even[0] = Mint{1};
for (int t = 1; t <= k; ++t) {
if (t % 2 == 1) {
for (int j = 0; j <= n / 2; ++j) {
for (int kk = 0; kk <= n / 2; ++kk) {
odd[j][kk] = Mint{0};
for (int i = std::max(2 * j, 2 * kk); i <= n; ++i) {
odd[j][kk] += (Mint::comb(i, 2 * j) * h[2 * j]) *
(Mint::comb(i, 2 * kk) * h[2 * kk]) *
f[2 * (n - i)][i - 2 * j][i - 2 * kk] * even[i];
}
}
}
} else {
for (int i = 0; i <= n; ++i) {
even[i] = Mint{0};
for (int j = 0; j <= std::min(n / 2, i); ++j) {
for (int kk = 0; kk <= std::min(n / 2, i); ++kk) {
if (n + j + kk - 2 * i >= 0) {
int nl = n + kk - j;
int nr = n + j - kk;
even[i] += g[nl - j][j][i - j] * g[nr - kk][kk][i - kk] *
Mint::fac(n + j + kk - 2 * i) * odd[j][kk];
}
}
}
}
}
}
Mint ans{0};
if (k % 2 == 0) {
for (Mint v : even) {
ans += v;
}
} else {
for (auto& arr : odd) {
for (Mint v : arr) {
ans += v;
}
}
}
std::cout << ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 56ms
memory: 36068kb
input:
3 1 1000000007
output:
15
result:
ok single line: '15'
Test #2:
score: 0
Accepted
time: 89ms
memory: 48236kb
input:
100 3 1000000007
output:
894710378
result:
ok single line: '894710378'
Test #3:
score: 0
Accepted
time: 56ms
memory: 36068kb
input:
6 6 1000000007
output:
103387851
result:
ok single line: '103387851'
Test #4:
score: 0
Accepted
time: 57ms
memory: 36196kb
input:
2 6 998244353
output:
729
result:
ok single line: '729'
Test #5:
score: 0
Accepted
time: 4848ms
memory: 731920kb
input:
400 20 713862469
output:
561801910
result:
ok single line: '561801910'
Test #6:
score: 0
Accepted
time: 4203ms
memory: 716500kb
input:
397 17 861815723
output:
764050494
result:
ok single line: '764050494'
Test #7:
score: 0
Accepted
time: 3575ms
memory: 686704kb
input:
391 14 189546607
output:
131011086
result:
ok single line: '131011086'
Test #8:
score: 0
Accepted
time: 2890ms
memory: 643460kb
input:
382 11 922402597
output:
58290636
result:
ok single line: '58290636'
Test #9:
score: 0
Accepted
time: 2260ms
memory: 588680kb
input:
370 8 911997731
output:
823449745
result:
ok single line: '823449745'
Test #10:
score: 0
Accepted
time: 1636ms
memory: 525192kb
input:
355 5 708230279
output:
173013324
result:
ok single line: '173013324'
Test #11:
score: 0
Accepted
time: 2754ms
memory: 455556kb
input:
337 19 742344989
output:
592413780
result:
ok single line: '592413780'
Test #12:
score: 0
Accepted
time: 2413ms
memory: 444552kb
input:
334 16 816423319
output:
567577272
result:
ok single line: '567577272'
Test #13:
score: 0
Accepted
time: 2015ms
memory: 423428kb
input:
328 13 463459417
output:
77314092
result:
ok single line: '77314092'
Test #14:
score: 0
Accepted
time: 1595ms
memory: 392960kb
input:
319 10 469180903
output:
94351928
result:
ok single line: '94351928'
Test #15:
score: 0
Accepted
time: 1211ms
memory: 354692kb
input:
307 7 240226001
output:
147458009
result:
ok single line: '147458009'
Test #16:
score: 0
Accepted
time: 881ms
memory: 311168kb
input:
292 4 725635439
output:
275908993
result:
ok single line: '275908993'
Test #17:
score: 0
Accepted
time: 1442ms
memory: 264192kb
input:
274 18 518962097
output:
200937333
result:
ok single line: '200937333'
Test #18:
score: 0
Accepted
time: 1223ms
memory: 256900kb
input:
271 15 765905797
output:
683367155
result:
ok single line: '683367155'
Test #19:
score: 0
Accepted
time: 1015ms
memory: 242564kb
input:
265 12 240076537
output:
6822852
result:
ok single line: '6822852'
Test #20:
score: 0
Accepted
time: 803ms
memory: 222848kb
input:
256 9 319057337
output:
9076486
result:
ok single line: '9076486'
Test #21:
score: 0
Accepted
time: 574ms
memory: 198396kb
input:
244 6 257631131
output:
53842743
result:
ok single line: '53842743'
Test #22:
score: 0
Accepted
time: 415ms
memory: 170876kb
input:
229 3 953863681
output:
247424565
result:
ok single line: '247424565'
Test #23:
score: 0
Accepted
time: 57ms
memory: 36196kb
input:
1 20 998244353
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 58ms
memory: 36200kb
input:
8 4 998244353
output:
740255777
result:
ok single line: '740255777'
Test #25:
score: 0
Accepted
time: 56ms
memory: 36200kb
input:
5 20 998244353
output:
725931122
result:
ok single line: '725931122'
Test #26:
score: 0
Accepted
time: 1693ms
memory: 732044kb
input:
400 1 1000000007
output:
705610633
result:
ok single line: '705610633'
Test #27:
score: 0
Accepted
time: 1843ms
memory: 732000kb
input:
400 2 1000000007
output:
917456162
result:
ok single line: '917456162'
Test #28:
score: 0
Accepted
time: 57ms
memory: 36196kb
input:
1 1 1000000007
output:
1
result:
ok single line: '1'
Extra Test:
score: 0
Extra Test Passed