QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#715300 | #9476. 012 Grid | definieren | AC ✓ | 350ms | 25960kb | C++14 | 13.8kb | 2024-11-06 11:23:30 | 2024-11-06 11:23:31 |
Judging History
answer
#include <bits/stdc++.h>
#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n'
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define dbg(x) void()
#define dpi(x, y) void()
#define dbgf(fmt, args...) void()
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ldb = long double;
using i128 = __int128_t;
using ui128 = __uint128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;
bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T Norm(T a, T p = MOD) { return (a % p + p) % p; }
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T> T DivFloor(T a, T b) { return a >= 0 ? a / b : (a - b + 1) / b; }
template<typename T> T DivCeil(T a, T b) { return a >= 0 ? (a + b - 1) / b : a / b; }
namespace FastIO {
constexpr int LEN = 1 << 20;
char in[LEN + 1], out[LEN + 1];
char *pin = in, *pout = out, *ein = in, *eout = out + LEN;
char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
struct Flush { ~Flush() { fwrite(out, 1, pout - out, stdout); pout = out; return; } } _flush;
template<typename T> T Read() {
T x = 0; int f = 1; char ch = gc();
while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return x * f;
}
void Read(char *s) {
char ch = gc();
while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = gc();
while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')) *s = ch, s ++, ch = gc();
*s = '\0'; return;
}
template<typename T> void Read(T &x) { x = Read<T>(); return; }
template<typename T, typename ...Args>
void Read(T &x, Args &...args) { Read(x), Read(args...); return; }
template<typename T> void Write(T x) {
static char stk[40]; int tp = 0;
if (x < 0) pc('-'), x = ~x + 1;
do stk[tp++] = x % 10 + 48, x /= 10; while (x);
while (tp --) pc(stk[tp]);
return;
}
void Write(char ch) { pc(ch); return; }
void Write(const char *s) {
while (*s != '\0') pc(*s), s ++;
return;
}
void Puts(const char *s) {
Write(s), pc('\n'); return;
}
template<typename T, typename ...Args>
void Write(T x, Args ...args) { Write(x), Write(args...); return; }
}
using FastIO::Read;
using FastIO::Write;
using FastIO::Puts;
#define getchar FastIO::gc
#define putchar FastIO::pc
template<int P>
struct Modint {
int x; static int Mod;
constexpr Modint(): x(0) { return; }
constexpr Modint(ll _x): x(norm(_x % GetMod())) { return; }
constexpr static int GetMod() { return P ? P : Mod; }
constexpr static void SetMod(int _Mo) { Mod = _Mo; return; }
explicit constexpr operator int() const { return x; }
operator bool() const { return x; }
Modint inv() const { return (*this) ^ (GetMod() - 2); }
constexpr int norm(int x) const { if (x < 0) x += GetMod(); if (x >= GetMod()) x -= GetMod(); return x; }
friend Modint operator - (Modint x) { x.x = x.norm(GetMod() - x.x); return x; }
Modint &operator += (const Modint &oth) { x = norm(x + oth.x); return *this; }
Modint &operator -= (const Modint &oth) { x = norm(x - oth.x); return *this; }
Modint &operator *= (const Modint &oth) { x = 1ll * x * oth.x % GetMod(); return *this; }
Modint &operator /= (const Modint &oth) { x = 1ll * x * oth.inv().x % GetMod(); return *this; }
Modint &operator ^= (const ll &y) { return (*this) = (*this) ^ y; }
Modint &operator ^= (const int &y) { return (*this) = (*this) ^ y; }
Modint &operator ++ () { return (*this) += 1; }
Modint &operator -- () { return (*this) -= 1; }
Modint operator ++ (int) { Modint tmp = (*this); return ++ (*this), tmp; }
Modint operator -- (int) { Modint tmp = (*this); return -- (*this), tmp; }
friend Modint operator + (Modint x, const Modint &y) { return x += y; }
friend Modint operator - (Modint x, const Modint &y) { return x -= y; }
friend Modint operator * (Modint x, const Modint &y) { return x *= y; }
friend Modint operator / (Modint x, const Modint &y) { return x /= y; }
friend Modint operator ^ (Modint x, ll y) { Modint ans = 1; for (; y; y >>= 1, x *= x) if (y & 1) ans *= x; return ans; }
friend Modint operator ^ (Modint x, int y) { return x ^= (ll)y; }
friend Modint operator + (Modint x, const int &y) { return x += Modint(y); }
friend Modint operator - (Modint x, const int &y) { return x -= Modint(y); }
friend Modint operator * (Modint x, const int &y) { return x *= Modint(y); }
friend Modint operator / (Modint x, const int &y) { return x /= Modint(y); }
friend Modint operator + (int x, const Modint &y) { return Modint(x) += y; }
friend Modint operator - (int x, const Modint &y) { return Modint(x) -= y; }
friend Modint operator * (int x, const Modint &y) { return Modint(x) *= y; }
friend Modint operator / (int x, const Modint &y) { return Modint(x) /= y; }
friend ostream& operator << (ostream& os, const Modint &x) { os << (int)x; return os; }
friend bool operator == (const Modint &x, const Modint &y) { return (int)x == (int)y; }
friend bool operator != (const Modint &x, const Modint &y) { return (int)x != (int)y; }
friend bool operator <= (const Modint &x, const Modint &y) { return (int)x <= (int)y; }
friend bool operator >= (const Modint &x, const Modint &y) { return (int)x >= (int)y; }
friend bool operator < (const Modint &x, const Modint &y) { return (int)x < (int)y; }
friend bool operator > (const Modint &x, const Modint &y) { return (int)x > (int)y; }
};
template<> int Modint<0>::Mod = 998244353;
using mint = Modint<0>;
struct Combination {
int N;
vector<mint> _fac, _ifac, _inv;
Combination(int n) { Init(n); return; }
Combination(): N(0), _fac{1}, _ifac{1}, _inv{0} { return; }
void Init(int n) {
if (n <= N) return;
_fac.resize(n + 1), _ifac.resize(n + 1), _inv.resize(n + 1);
for (int i = N + 1; i <= n; i ++) _fac[i] = _fac[i - 1] * i;
_ifac[n] = _fac[n].inv();
for (int i = n; i > N; i --) _ifac[i - 1] = _ifac[i] * i,
_inv[i] = _ifac[i] * _fac[i - 1];
N = n; return;
}
mint fac(int n) {
if (n > N) Init(n << 1);
return _fac[n];
}
mint ifac(int n) {
if (n > N) Init(n << 1);
return _ifac[n];
}
mint inv(int n) {
if (n > N) Init(n << 1);
return _inv[n];
}
mint C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return fac(n) * ifac(m) * ifac(n - m);
}
} comb;
namespace Polynomial {
constexpr int Mod = 998244353, g = 3, inv2 = (MOD + 1) >> 1;
vector<int> rev;
vector<mint> w{0, 1};
void DFT(vector<mint> &a) {
int n = (int)a.size();
if ((int)rev.size() != n) {
int k = __lg(n) - 1; rev.resize(n);
for (int i = 0; i < n; i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
}
if ((int)w.size() < n) {
int k = __lg(w.size()); w.resize(n);
while (1 << k < n) {
mint e = mint(g) ^ ((Mod - 1) >> (k + 1));
for (int i = 1 << (k - 1); i < 1 << k; i ++)
w[i << 1] = w[i], w[i << 1 | 1] = w[i] * e;
k ++;
}
}
for (int i = 0; i < n; i ++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k <<= 1)
for (int i = 0; i < n; i += k << 1)
for (int j = 0; j < k; j ++) {
mint u = a[i | j], v = a[i | j | k] * w[j | k];
a[i | j] = u + v, a[i | j | k] = u - v;
}
return;
}
void IDFT(vector<mint> &a) {
int n = (int)a.size();
reverse(a.begin() + 1, a.end());
DFT(a); mint inv = (1 - Mod) / n;
for (int i = 0; i < n; i ++) a[i] *= inv;
return;
}
struct Poly : public vector<mint> {
Poly(): vector<mint>() { return; }
explicit Poly(int n): vector<mint>(n) { return; }
explicit Poly(const vector<mint> &a): vector<mint>(a) { return; }
Poly(const initializer_list<mint> &a): vector<mint>(a) { return; }
template<class _InputIterator, class = std::_RequireInputIter<_InputIterator>>
explicit constexpr Poly(_InputIterator __first, _InputIterator __last): vector<mint>(__first, __last) { return; }
template<class F> explicit constexpr Poly(int n, F f): vector<mint>(n) {
for (int i = 0; i < n; i ++) (*this)[i] = f(i);
return;
}
Poly Shift(int k) const {
if (k >= 0) { auto ret = *this; ret.insert(ret.begin(), k, mint(0)); return ret; }
else return (int)this -> size() <= - k ? Poly() : Poly(this -> begin() - k, this -> end());
}
Poly Trunc(int k) const {
Poly f = *this; f.resize(k); return f;
}
friend Poly operator + (const Poly &f, const Poly &g) {
Poly ret(max(f.size(), g.size()));
for (int i = 0; i < (int)f.size(); i ++) ret[i] = f[i];
for (int i = 0; i < (int)g.size(); i ++) ret[i] += g[i];
return ret;
}
friend Poly operator - (const Poly &f, const Poly &g) {
Poly ret(max(f.size(), g.size()));
for (int i = 0; i < (int)f.size(); i ++) ret[i] = f[i];
for (int i = 0; i < (int)g.size(); i ++) ret[i] -= g[i];
return ret;
}
friend Poly operator - (const Poly &f) {
Poly ret(f.size());
for (int i = 0; i < (int)ret.size(); i ++) ret[i] = - f[i];
return ret;
}
friend Poly operator * (Poly f, Poly g) {
if (!f.size() || !g.size()) return Poly();
if (f.size() < g.size()) std::swap(f, g);
int n = 1, m = (int)f.size() + (int)g.size() - 1;
if (g.size() < 1 << 7) {
Poly ret(m);
for (int i = 0; i < (int)f.size(); i ++)
for (int j = 0; j < (int)g.size(); j ++)
ret[i + j] += f[i] * g[j];
return ret;
}
while (n < m) n <<= 1;
f.resize(n), g.resize(n), DFT(f), DFT(g);
for (int i = 0; i < n; i ++) f[i] *= g[i];
IDFT(f), f.resize(m); return f;
}
friend Poly operator * (Poly f, mint x) {
for (int i = 0; i < (int)f.size(); i ++) f[i] *= x;
return f;
}
friend Poly operator * (mint x, Poly f) {
for (int i = 0; i < (int)f.size(); i ++) f[i] *= x;
return f;
}
friend Poly operator / (Poly f, mint x) {
for (int i = 0; i < (int)f.size(); i ++) f[i] /= x;
return f;
}
Poly& operator += (Poly oth) { return (*this) = (*this) + oth; }
Poly& operator -= (Poly oth) { return (*this) = (*this) - oth; }
Poly& operator *= (Poly oth) { return (*this) = (*this) * oth; }
Poly& operator *= (mint oth) { return (*this) = (*this) * oth; }
Poly& operator /= (mint oth) { return (*this) = (*this) / oth; }
Poly Inv(int lim) const {
Poly f{(*this)[0].inv()}; int k = 1;
while (k < lim) k <<= 1, f = (f * (Poly{2}- Trunc(k) * f)).Trunc(k);
return f.Trunc(lim);
}
Poly Deriv() const {
if (this -> empty()) return Poly();
Poly f(this -> size() - 1);
for (int i = 0; i < (int)f.size(); i ++)
f[i] = (i + 1) * (*this)[i + 1];
return f;
}
Poly Integr() const {
Poly f(this -> size() + 1);
for (int i = 0; i < (int)this -> size(); i ++)
f[i + 1] = (*this)[i] / (i + 1);
return f;
}
Poly Log(int lim) const {
return (Deriv() * Inv(lim)).Integr().Trunc(lim);
}
Poly Exp(int lim) const {
Poly f{1}; int k = 1;
while (k < lim) k <<= 1, f = (f * (Poly{1} - f.Log(k) + Trunc(k))).Trunc(k);
return f.Trunc(lim);
}
Poly Pow(int k, int lim) const {
int i = 0;
while (i < (int)this -> size() && !(*this)[i]) i ++;
if (i == (int)this -> size() || 1ll * i * k >= lim) return Poly(lim);
mint v = (*this)[i]; Poly f = Shift(- i) * v.inv();
return (f.Log(lim - i * k) * k).Exp(lim - i * k).Shift(i * k) * (v ^ k);
}
Poly Sqrt(int lim) const {
Poly f{1}; int k = 1;
while (k < lim) k <<= 1, f = (f + (Trunc(k) * f.Inv(k)).Trunc(k)) * inv2;
return f.Trunc(lim);
}
};
} using Polynomial::Poly;
constexpr int N = 2e5 + 5;
int n, m;
void slv() {
Read(n, m); mint ans = 2;
auto calc = [&](int n, int m) {
return comb.C(n + m - 2, n - 1) * comb.C(n + m - 2, m - 1)
- comb.C(n + m - 2, n) * comb.C(n + m - 2, m);
};
for (int i = 1; i <= n; i ++) ans += calc(i, m) * (n - i + 1);
for (int j = 1; j < m; j ++) ans += calc(n, j) * (m - j + 1);
if (-- n >= 1 && -- m >= 1) {
Poly F(n), G(m);
for (int i = 0; i < n; i ++) F[i] = comb.ifac(i) * comb.ifac(i);
for (int i = 0; i < m; i ++) G[i] = comb.ifac(i) * comb.ifac(i);
F *= G;
for (int i = 0; i < n + m - 1; i ++)
ans += F[i] * comb.fac(i) * comb.fac(i) * 2;
F.resize(n), F[0] = G[0] = 0;
for (int i = 1; i < n; i ++) F[i] = comb.ifac(i - 1) * comb.ifac(i + 1);
for (int i = 1; i < m; i ++) G[i] = comb.ifac(i - 1) * comb.ifac(i + 1);
F *= G;
for (int i = 0; i < n + m - 1; i ++)
ans -= F[i] * comb.fac(i) * comb.fac(i) * 2;
}
Write((int)ans, '\n');
return;
}
void clr() {
return;
}
bool Med;
int main() {
#ifdef LOCAL
freopen("!in.in", "r", stdin);
freopen("!out.out", "w", stdout);
fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
int T = 1;
// int T = Read<int>();
while (T --) slv(), clr();
#ifdef LOCAL
fprintf(stderr, "%d ms\n", (int)clock());
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 350ms
memory: 25812kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 9ms
memory: 3864kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 8ms
memory: 3680kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 8ms
memory: 3924kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 8ms
memory: 3984kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 8ms
memory: 3728kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 9ms
memory: 3780kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 6ms
memory: 4196kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 6ms
memory: 3880kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 6ms
memory: 3928kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 9ms
memory: 3944kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 334ms
memory: 20504kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 159ms
memory: 13404kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 158ms
memory: 11784kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 77ms
memory: 8380kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 336ms
memory: 23828kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 163ms
memory: 14600kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 159ms
memory: 12488kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 150ms
memory: 10668kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 151ms
memory: 10852kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 157ms
memory: 15332kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 341ms
memory: 25880kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 346ms
memory: 25960kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 345ms
memory: 25960kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 8ms
memory: 5392kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 11ms
memory: 6016kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed