QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#837435 | #1257. Easy One | ucup-team004 | AC ✓ | 29ms | 28856kb | C++23 | 8.4kb | 2024-12-30 03:52:55 | 2024-12-30 03:52:56 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
template<class T>
constexpr T power(T a, u64 b, T res = 1) {
for (; b != 0; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
return u64(a) * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
constexpr i64 safeMod(i64 x, i64 m) {
x %= m;
if (x < 0) {
x += m;
}
return x;
}
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
a = safeMod(a, b);
if (a == 0) {
return {b, 0};
}
i64 s = b, t = a;
i64 m0 = 0, m1 = 1;
while (t) {
i64 u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) {
m0 += b / s;
}
return {s, m0};
}
template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
constexpr ModIntBase() : x(0) {}
template<std::unsigned_integral T>
constexpr ModIntBase(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr ModIntBase(T x_) {
using S = std::make_signed_t<U>;
S v = x_ % S(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static U mod() {
return P;
}
constexpr U val() const {
return x;
}
constexpr ModIntBase operator-() const {
ModIntBase res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr ModIntBase inv() const {
return power(*this, mod() - 2);
}
constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
x = mulMod<mod()>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
return *this *= rhs.inv();
}
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
return os << a.val();
}
friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() <=> rhs.val();
}
private:
U x;
};
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
struct Barrett {
public:
Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}
constexpr u32 mod() const {
return m;
}
constexpr u32 mul(u32 a, u32 b) const {
u64 z = a;
z *= b;
u64 x = u64((u128(z) * im) >> 64);
u32 v = u32(z - x * m);
if (m <= v) {
v += m;
}
return v;
}
private:
u32 m;
u64 im;
};
template<u32 Id>
struct DynModInt {
public:
constexpr DynModInt() : x(0) {}
template<std::unsigned_integral T>
constexpr DynModInt(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr DynModInt(T x_) {
int v = x_ % int(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static void setMod(u32 m) {
bt = m;
}
static u32 mod() {
return bt.mod();
}
constexpr u32 val() const {
return x;
}
constexpr DynModInt operator-() const {
DynModInt res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr DynModInt inv() const {
auto v = invGcd(x, mod());
assert(v.first == 1);
return v.second;
}
constexpr DynModInt &operator*=(const DynModInt &rhs) & {
x = bt.mul(x, rhs.val());
return *this;
}
constexpr DynModInt &operator+=(const DynModInt &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr DynModInt &operator-=(const DynModInt &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr DynModInt &operator/=(const DynModInt &rhs) & {
return *this *= rhs.inv();
}
friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
return os << a.val();
}
friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() <=> rhs.val();
}
private:
u32 x;
static Barrett bt;
};
template<u32 Id>
Barrett DynModInt<Id>::bt = 998244353;
using Z = ModInt<998244353>;
struct Comb {
int n;
std::vector<Z> _fac;
std::vector<Z> _invfac;
std::vector<Z> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
} comb;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int a, b, t;
std::cin >> a >> b >> t;
if (t % 2 || t < 2 * std::abs(b - a)) {
std::cout << 0 << "\n";
return 0;
}
t /= 2;
Z ans = 0;
for (int i = 0; i <= a; i++) {
ans += comb.binom(t, b - a + i) * comb.binom(t + (b - a + i), i) * comb.binom(b, b - a + i);
}
for (int i = 1; i <= t; i++) {
ans *= 2 * i - 1;
}
std::cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
0 0 4
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 4 6
output:
60
result:
ok 1 number(s): "60"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10 10 9
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
123 456 999
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
123 456 1000
output:
217690319
result:
ok 1 number(s): "217690319"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
0 999999 999999
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 10ms
memory: 14704kb
input:
0 499999 999998
output:
441249169
result:
ok 1 number(s): "441249169"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
999999 999999 999999
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 22ms
memory: 26536kb
input:
999999 999999 999998
output:
94264534
result:
ok 1 number(s): "94264534"
Test #10:
score: 0
Accepted
time: 6ms
memory: 14848kb
input:
500000 500000 10
output:
278436239
result:
ok 1 number(s): "278436239"
Test #11:
score: 0
Accepted
time: 23ms
memory: 28856kb
input:
123456 567890 999998
output:
200851796
result:
ok 1 number(s): "200851796"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
123456 565444 676767
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
999999 999999 121233
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 24ms
memory: 26444kb
input:
999999 999999 500000
output:
31235134
result:
ok 1 number(s): "31235134"
Test #15:
score: 0
Accepted
time: 27ms
memory: 28608kb
input:
999997 999993 500002
output:
289239002
result:
ok 1 number(s): "289239002"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
99999 999999 990000
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
0 499999 999996
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 12ms
memory: 14932kb
input:
0 0 1000000
output:
765860359
result:
ok 1 number(s): "765860359"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
0 1000000 0
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
0 1000000 1000000
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1000000 0 0
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1000000 0 1000000
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 25ms
memory: 26612kb
input:
1000000 1000000 0
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 29ms
memory: 26472kb
input:
1000000 1000000 1000000
output:
657734828
result:
ok 1 number(s): "657734828"
Test #26:
score: 0
Accepted
time: 3ms
memory: 7348kb
input:
42153 66017 282528
output:
721725208
result:
ok 1 number(s): "721725208"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
920225 95518 314790
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
761297 88021 384736
output:
0
result:
ok 1 number(s): "0"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
639368 117522 379998
output:
0
result:
ok 1 number(s): "0"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
480440 110024 375261
output:
0
result:
ok 1 number(s): "0"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
321512 138841 445207
output:
0
result:
ok 1 number(s): "0"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
199583 168342 440469
output:
0
result:
ok 1 number(s): "0"
Test #33:
score: 0
Accepted
time: 3ms
memory: 12476kb
input:
40655 160844 473416
output:
740459120
result:
ok 1 number(s): "740459120"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
881728 190346 468679
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
722801 219847 538624
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
140788 795655 506181
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 22ms
memory: 22700kb
input:
981861 788157 538442
output:
985234443
result:
ok 1 number(s): "985234443"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
822934 817658 571389
output:
0
result:
ok 1 number(s): "0"
Test #39:
score: 0
Accepted
time: 17ms
memory: 18628kb
input:
664006 772477 566652
output:
652080352
result:
ok 1 number(s): "652080352"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
542077 838977 636597
output:
0
result:
ok 1 number(s): "0"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
346150 868479 631860
output:
0
result:
ok 1 number(s): "0"
Test #42:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
224221 860981 664806
output:
0
result:
ok 1 number(s): "0"
Test #43:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
65293 890482 697068
output:
0
result:
ok 1 number(s): "0"
Test #44:
score: 0
Accepted
time: 28ms
memory: 26140kb
input:
943365 882985 729330
output:
351354011
result:
ok 1 number(s): "351354011"
Test #45:
score: 0
Accepted
time: 21ms
memory: 21444kb
input:
784437 911801 762276
output:
155945330
result:
ok 1 number(s): "155945330"
Test #46:
score: 0
Accepted
time: 14ms
memory: 19672kb
input:
491726 307429 671948
output:
73584358
result:
ok 1 number(s): "73584358"
Test #47:
score: 0
Accepted
time: 18ms
memory: 19152kb
input:
295799 336931 704894
output:
534052287
result:
ok 1 number(s): "534052287"
Test #48:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
173870 403431 700157
output:
0
result:
ok 1 number(s): "0"
Test #49:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
14942 395934 770103
output:
0
result:
ok 1 number(s): "0"
Test #50:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
893014 387751 765365
output:
0
result:
ok 1 number(s): "0"
Test #51:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
697087 380253 797627
output:
0
result:
ok 1 number(s): "0"
Test #52:
score: 0
Accepted
time: 11ms
memory: 16912kb
input:
575158 409755 830574
output:
261071668
result:
ok 1 number(s): "261071668"
Test #53:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
416230 476255 862835
output:
0
result:
ok 1 number(s): "0"
Test #54:
score: 0
Accepted
time: 20ms
memory: 20772kb
input:
257303 468757 895782
output:
86924988
result:
ok 1 number(s): "86924988"
Test #55:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
135374 498259 891045
output:
0
result:
ok 1 number(s): "0"
Test #56:
score: 0
Accepted
time: 24ms
memory: 21896kb
input:
805665 893203 838400
output:
263337727
result:
ok 1 number(s): "263337727"
Test #57:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
729675 247218 434658
output:
0
result:
ok 1 number(s): "0"
Test #58:
score: 0
Accepted
time: 19ms
memory: 17292kb
input:
609216 669503 870072
output:
202261436
result:
ok 1 number(s): "202261436"
Test #59:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
488756 514031 929421
output:
0
result:
ok 1 number(s): "0"
Test #60:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
691776 682039 463599
output:
0
result:
ok 1 number(s): "0"
Test #61:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
571316 404780 199469
output:
0
result:
ok 1 number(s): "0"
Test #62:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
774336 249308 958362
output:
0
result:
ok 1 number(s): "0"
Test #63:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
330396 671592 116476
output:
0
result:
ok 1 number(s): "0"
Test #64:
score: 0
Accepted
time: 24ms
memory: 22736kb
input:
533416 516121 753582
output:
113683116
result:
ok 1 number(s): "113683116"
Test #65:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
412956 684129 287759
output:
0
result:
ok 1 number(s): "0"
Test #66:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
292496 406870 347109
output:
0
result:
ok 1 number(s): "0"
Test #67:
score: 0
Accepted
time: 9ms
memory: 10980kb
input:
245891 134953 893416
output:
299302885
result:
ok 1 number(s): "299302885"
Test #68:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
125431 880717 952766
output:
0
result:
ok 1 number(s): "0"
Test #69:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
906207 725245 810423
output:
0
result:
ok 1 number(s): "0"
Test #70:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
207991 569774 546293
output:
0
result:
ok 1 number(s): "0"
Test #71:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
665287 992058 981707
output:
0
result:
ok 1 number(s): "0"
Test #72:
score: 0
Accepted
time: 18ms
memory: 23068kb
input:
868307 836586 139820
output:
168754021
result:
ok 1 number(s): "168754021"
Test #73:
score: 0
Accepted
time: 20ms
memory: 20728kb
input:
747847 882807 776926
output:
679383214
result:
ok 1 number(s): "679383214"