QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#655809 | #9476. 012 Grid | ucup-team3931# | RE | 216ms | 27148kb | C++20 | 12.6kb | 2024-10-19 09:46:03 | 2024-10-19 09:46:03 |
Judging History
answer
#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
using vi = vector<int>;
#endif
namespace Math {
constexpr int P = 998244353;
constexpr int G = 3;
#ifdef _WIN32
using uint = uint32_t;
#endif
using ull = uint64_t;
using cint = const int;
template<class T>
IL void qm (T &x) {
x += (x >> 31) & P;
}
template<class T>
IL T nor (const T &x) {
return x + ((x >> 31) & P);
}
template<class T>
IL T fix (T x) {
return nor(x %= P);
}
IL int qpow (int b, int k) {
int r = 1;
for (; k; k >>= 1, b = (ull)b * b % P) if (k & 1) r = (ull)r * b % P;
return r;
}
namespace FFT {
constexpr int N = 1 << 20;
int n, lg, root[N];
IL void init (cint z) {
n = 1, lg = 0;
while (n <= z) {
n <<= 1;
++lg;
}
assert(n <= N);
ull w = qpow(G, (P - 1) / n);
root[0] = 1;
for (int i = 1; i < n; ++i) {
root[i] = root[i - 1] * w % P;
}
}
template<typename T>
IL void DIF (T *a) {
static int *i, *j;
for (int l = n; l > 1; l >>= 1) {
cint m = l >> 1;
for (i = a; i != a + n; i += l) {
int *w = root;
for (j = i; j != i + m; ++j, w += n / l) {
T t = nor(*j + j[m] - P);
j[m] = (ull)*w * (*j - j[m] + P) % P;
*j = t;
}
}
}
}
template<typename T>
IL void DIT (T *a) {
static int *i, *j;
for (int l = 2; l <= n; l <<= 1) {
cint m = l >> 1;
for (i = a; i != a + n; i += l) {
int *w = root;
for (j = i; j != i + m; ++j, w += n / l) {
T t = (ull)*w * j[m] % P;
qm(j[m] = *j - t);
qm(*j += t - P);
}
}
}
T iv = P - (P - 1) / n;
reverse(a + 1, a + n);
for (int i = 0; i < n; i++) {
a[i] = (ull)a[i] * iv % P;
}
}
}
using FFT::init;
using FFT::DIF;
using FFT::DIT;
struct Poly {
vector<int> a;
Poly () : a(1) {}
Poly (int v) { fix(v); a = {v}; }
Poly (vector<int> &a) : a(a) {}
Poly (initializer_list<int> a) : a(a) {}
int operator [] (uint p) const {
return p < a.size() ? a[p] : 0;
}
int& operator [] (uint p) {
return p < a.size() ? a[p] : (a.resize(p + 1), a[p]);
}
const size_t deg () const { return a.size() - 1; }
const size_t size () const { return a.size(); }
int *base () { return a.data(); }
cint *base () const { return a.data(); }
void redeg (size_t d) { a.resize(d + 1); }
void resize (size_t sz) { a.resize(sz); }
Poly slice (int d) const {
if (d < (int)(a.size())) {
vector<int> r(a.begin(), a.begin() + d);
return r;
}
vector<int> r(a);
r.resize(d);
return r;
}
Poly operator + (const Poly &z) const {
vector<int> r(max(a.size(), z.a.size()));
for (int i = 0; i < (int)(r.size()); i++) {
qm(r[i] = operator[](i) + z[i] - P);
}
return r;
}
Poly operator - (const Poly &z) const {
vector<int> r(max(a.size(), z.a.size()));
for (int i = 0; i < (int)(r.size()); i++) {
qm(r[i] = operator[](i) - z[i]);
}
return r;
}
Poly operator - () const {
vector<int> r(a);
for (auto &v : r) {
if (v) {
v = P - v;
}
}
return r;
}
Poly deriv () const {
int _n = deg();
if (!_n) {
return 0;
} else {
vector<int> r(_n);
for (int i = 0; i < _n; i++) {
r[i] = (ull)a[i + 1] * (i + 1) % P;
}
return r;
}
}
Poly integ () const {
static vector<int> iv{0, 1};
int _n = size();
if (_n >= (int)(iv.size())) {
int _m = iv.size();
iv.resize(_n + 1);
for (int i = _m; i <= _n; i++) {
iv[i] = (ull)iv[P % i] * (P - P / i) % P;
}
}
vector<int> r(_n + 1);
for (int i = 1; i <= _n; i++) {
r[i] = (ull)a[i - 1] * iv[i] % P;
}
return r;
}
Poly T () const {
Poly z = *this;
reverse(z.a.begin(), z.a.end());
return z;
}
Poly operator * (const Poly &z) const;
Poly inv () const;
Poly operator / (const Poly &z) const {
size_t n = deg(), m = z.deg();
if (n < m) {
return Poly();
}
Poly F = T(), G = z.T();
F.redeg(n - m), G.redeg(n - m);
Poly Q = F * G.inv();
Q.redeg(n - m);
return Q.T();
}
Poly operator % (const Poly &z) const {
Poly R = *this - *this / z * z;
R.resize(z.deg());
return R;
}
Poly& operator += (const Poly &z) { (*this) = (*this) + z; return *this; }
Poly& operator -= (const Poly &z) { (*this) = (*this) - z; return *this; }
Poly& operator *= (const Poly &z) { (*this) = (*this) * z; return *this; }
Poly& operator /= (const Poly &z) { (*this) = (*this) / z; return *this; }
Poly& operator %= (const Poly &z) { (*this) = (*this) % z; return *this; }
Poly ln () const;
Poly exp () const;
Poly sqrt () const;
Poly pow (int k) const {
Poly b = *this, r = 1;
for (; k; k >>= 1, b *= b) if (k & 1) r *= b;
return r;
}
};
IL Poly _bfmul (const Poly &a, const Poly &b) {
int n = a.size(), m = b.size();
vector<int> c(n + m - 1);
for (int i = 0; i < n; i++) {
if (a[i]) {
for (int j = 0; j < m; j++) {
c[i + j] = (c[i + j] + (ull)a[i] * b[j]) % P;
}
}
}
return c;
}
IL Poly _mul (Poly a, Poly b) {
int n = a.size() + b.size() - 1;
FFT::init(n);
int _n = FFT::n;
a.resize(_n);
b.resize(_n);
DIF(a.base());
DIF(b.base());
Poly c(a);
for (int i = 0; i < _n; i++) {
c[i] = (ull)c[i] * b[i] % P;
}
DIT(c.base());
c.resize(n);
return c;
}
Poly Poly::operator* (const Poly &z) const {
int n = a.size(), m = z.size();
if (n <= 32 || m <= 32) {
return _bfmul(*this, z);
} else {
return _mul(*this, z);
}
}
namespace internal {
namespace Cipolla {
int w;
struct Complex {
int r, i;
Complex (int r = 0, int i = 0) : r(r), i(i) {}
Complex operator * (const Complex &rhs) const {
return Complex(((LL)r * rhs.r + (LL)i * rhs.i % P * w) % P,
((LL)r * rhs.i + (LL)i * rhs.r) % P);
}
Complex pow (int k) const {
Complex r(1, 0), b(*this);
for (; k; k >>= 1, b = b * b) if (k & 1) r = r * b;
return r;
}
};
mt19937 rng(random_device{}());
int Cipolla (int a) {
int b;
do {
b = rng() % P;
w = ((LL)b * b + P - a) % P;
} while (b == 0 || qpow(w, (P - 1) / 2) == 1);
int z = Complex(b, 1).pow((P + 1) / 2).r;
return min(z, P - z);
}
}
}
namespace Newton {
using FFT::init;
using FFT::DIF;
using FFT::DIT;
IL void inv (const Poly &f, Poly &g, cint l) {
if (l == 1) {
g = qpow(f[0], P - 2);
return;
}
inv(f, g, (l + 1) >> 1);
init(l << 1);
int _n = FFT::n;
Poly a = f.slice(l), b = g.slice(l);
a.resize(_n);
b.resize(_n);
DIF(a.base());
DIF(b.base());
vector<int> c(_n);
for (int i = 0; i < _n; i++) {
qm(c[i] = (int)((2 - (LL)a[i] * b[i]) % P * b[i] % P));
}
DIT(c.data());
g = Poly(c).slice(l);
}
IL void exp (const Poly &f, Poly &g, cint l) {
if (l == 1) {
assert(f[0] == 0);
g = 1;
return;
}
exp(f, g, (l + 1) >> 1);
Poly a = f.slice(l), b = g.slice(l);
Poly c = b * (Poly(1) - b.ln() + a);
g = c.slice(l);
}
IL void sqrt (const Poly &f, Poly &g, cint l) {
if (l == 1) {
g = internal::Cipolla::Cipolla(f[0]);
return;
}
sqrt(f, g, (l + 1) >> 1);
Poly a = f.slice(l), b = g.slice(l);
Poly c = (a + b * b) * (b * 2).inv();
g = c.slice(l);
}
}
Poly Poly::inv () const {
Poly s;
Newton::inv(*this, s, size());
return s;
}
Poly Poly::ln () const {
assert(a[0] == 1);
Poly s = (deriv() * inv()).integ();
s.redeg(deg());
return s;
}
Poly Poly::exp () const {
Poly s;
Newton::exp(*this, s, size());
return s;
}
Poly Poly::sqrt() const {
assert(qpow(a[0], (P - 1) / 2) == 1);
Poly s;
Newton::sqrt(*this, s, size());
return s;
}
namespace Ext {
vector<int> _eval (const Poly &f, const vector<int> &a, cint &n) {
static Poly t[1 << 20];
auto mul = [] (Poly a, Poly b) {
int n = a.size(), m = b.size();
reverse(b.a.begin(), b.a.end());
b *= a;
for (int i = 0; i < n; ++i) {
a[i] = b[m + i - 1];
}
return a;
};
auto dfs = [&] (auto self, int l, int r, int p) -> void {
if (r - l == 1) {
t[p] = {1, P - a[l]};
return;
}
int m = (l + r) >> 1;
self(self, l, m, p << 1);
self(self, m, r, p << 1 | 1);
t[p] = t[p << 1] * t[p << 1 | 1];
};
dfs(dfs, 0, n, 1);
vector<int> b(n);
auto conq = [&] (auto self, int l, int r, int p) -> void {
t[p].resize(r - l);
if (r - l == 1) {
b[l] = t[p][0];
return;
}
int m = (l + r) >> 1;
tie(t[p << 1], t[p << 1 | 1]) =
make_pair(mul(t[p], t[p << 1 | 1]), mul(t[p], t[p << 1]));
t[p] = Poly();
self(self, l, m, p << 1);
self(self, m, r, p << 1 | 1);
};
t[1] = mul(f, t[1].inv());
conq(conq, 0, n, 1);
return b;
}
vector<int> eval (const Poly &f, const vector<int> &a) {
int n = f.size(), m = a.size();
auto tf = f;
auto ta = a;
n = max(n, m);
tf.resize(n);
ta.resize(n);
auto b = _eval(tf, ta, n);
b.resize(m);
return b;
}
}
}
using Math::Poly;
constexpr int P = 998244353;
IL constexpr int qpow (int b, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, b = (LL)b * b % P) if (k & 1) r = (LL)r * b % P;
return r;
}
constexpr int N = 2e5 + 9;
int n, m;
int fc[N << 2], ifc[N << 2];
void init (int Z) {
fc[0] = 1;
L (i, 1, Z) {
fc[i] = (LL)fc[i - 1] * i % P;
}
ifc[Z] = qpow(fc[Z]);
R (i, Z - 1, 0) {
ifc[i] = (LL)ifc[i + 1] * (i + 1) % P;
}
}
int C (int n, int m) {
return n < m || m < 0 ? 0 : (LL)fc[n] * ifc[m] % P * ifc[n - m] % P;
}
int F (int n, int m) {
return C(n + m, n);
}
int G (int n, int m) {
return (F(n - 1, m - 1) * (LL)F(n - 1, m - 1) + (P - F(n - 2, m)) * (LL)F(n, m - 2)) % P;
}
int calc (int n) {
return n < 0 ? 0 : (C(2 * n, n) + P - C(2 * n, n - 2)) % P;
}
Poly A, B;
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
init((n + m) << 1);
LL ns = 0;
L (i, 0, n - 2) {
A[i] = (LL)ifc[i] * ifc[i] % P;
}
L (i, 0, m - 2) {
B[i] = (LL)ifc[i] * ifc[i] % P;
}
A *= B;
L (i, 0, n + m - 4) {
ns = (ns + 2LL * A[i] * fc[i] % P * fc[i]) % P;
}
A.redeg(n - 2);
B.redeg(m - 2);
L (i, 0, n - 2) {
A[i] = i ? (LL)ifc[i - 1] * ifc[i + 1] % P : 0;
}
L (i, 0, m - 2) {
B[i] = i ? (LL)ifc[i - 1] * ifc[i + 1] % P : 0;
}
A *= B;
L (i, 2, n + m - 4) {
ns = (ns + (P - 2LL) * A[i] % P * fc[i] % P * fc[i]) % P;
}
A.redeg(n - 1);
B.redeg(m - 1);
L (i, 0, n - 1) {
A[i] = !!i;
}
L (i, 0, m - 1) {
B[i] = !!i;
}
A *= A;
B *= B;
L (i, 2, 2 * n - 2) {
ns = (ns + (LL)A[i] * G(n - i, m)) % P;
}
L (i, 2, 2 * m - 2) {
ns = (ns + (LL)B[i] * G(n, m - i)) % P;
}
L (i, 1, n - 1) {
ns = (ns + 2LL * G(n - i, m)) % P;
}
L (i, 1, m - 1) {
ns = (ns + 2LL * G(n, m - i)) % P;
}
ns = (ns + G(n, m)) % P;
cout << (ns + 2) % P << '\n';
}
// I love WHQ!
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7680kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 202ms
memory: 24452kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7956kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7732kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7684kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 1ms
memory: 9688kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 1ms
memory: 9684kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 1ms
memory: 9768kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 1ms
memory: 10016kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 1ms
memory: 7932kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 1ms
memory: 7964kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 4ms
memory: 12272kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 3ms
memory: 10004kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 6ms
memory: 12248kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 6ms
memory: 9908kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 3ms
memory: 10008kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 3ms
memory: 12016kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 0ms
memory: 10084kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 4ms
memory: 10024kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 8ms
memory: 10176kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 8ms
memory: 10084kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 199ms
memory: 26064kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 97ms
memory: 18644kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 80ms
memory: 18420kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 53ms
memory: 18552kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 204ms
memory: 27148kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 112ms
memory: 22768kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 107ms
memory: 22828kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 75ms
memory: 18116kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 75ms
memory: 19656kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 114ms
memory: 24204kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 207ms
memory: 25636kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 211ms
memory: 26964kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 216ms
memory: 26512kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: -100
Runtime Error
input:
1 1