QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359319 | #7974. 染色 | wsyear | 100 ✓ | 438ms | 29212kb | C++14 | 3.2kb | 2024-03-20 16:18:15 | 2024-03-20 16:18:16 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
const int mod = 998244353;
const int iv2 = (mod + 1) >> 1;
const int maxn = 2000010;
int fpw(int a, int p = mod - 2) {
int res = 1;
while (p) {
if (p & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod, p >>= 1;
}
return res;
}
inline void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
inline int Add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
inline int Sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; }
int n, m, k, fac[maxn], ivf[maxn], f[maxn], g[maxn], rev[maxn];
void dft(int *a, int lim) {
int k = __builtin_ctz(lim);
rep (i, 1, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
rep (i, 0, lim - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int len = 1; len < lim; len <<= 1) {
int rt = fpw(3, (mod - 1) / (len << 1));
for (int l = 0; l < lim; l += (len << 1)) {
int wn = 1;
for (int i = 0; i < len; ++i, wn = 1ll * wn * rt % mod) {
int x = a[l + i], y = 1ll * a[l + i + len] * wn % mod;
a[l + i] = x + y, a[l + i + len] = x - y;
if (a[l + i] >= mod) a[l + i] -= mod;
if (a[l + i + len] < 0) a[l + i + len] += mod;
}
}
}
}
void idft(int *a, int lim) {
reverse(a + 1, a + lim), dft(a, lim);
int k = fpw(lim, mod - 2);
rep (i, 0, lim - 1) a[i] = 1ll * a[i] * k % mod;
}
int binom(int x, int y) {
if (x < 0 || y < 0 || x < y) return 0;
return 1ll * fac[x] * ivf[y] % mod * ivf[x - y] % mod;
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n >> m >> k;
fac[0] = 1;
rep (i, 1, n * m) fac[i] = 1ll * fac[i - 1] * i % mod;
ivf[n * m] = fpw(fac[n * m]);
per (i, n * m, 1) ivf[i - 1] = 1ll * ivf[i] * i % mod;
int ans = 0, lim = 1;
while (lim <= 2 * n * m) lim <<= 1;
rep (i, 0, n * m) if (k - i >= 0) f[i] = 1ll * ((i & 1) ? mod - 1 : 1) * ivf[i] % mod * ivf[k - i] % mod;
rep (i, 0, n * m) if (n * m - i - k >= 0) g[i] = 1ll * ivf[i] * ivf[n * m - i - k] % mod;
dft(f, lim), dft(g, lim);
rep (i, 0, lim - 1) f[i] = 1ll * f[i] * g[i] % mod;
idft(f, lim);
rep (x, 0, n) rep (y, 0, m) {
int cnt = x * (m - y) + y * (n - x);
// rep (p, 0, cnt) {
// if (k - p >= 0 && n * m - cnt - (k - p) >= 0)
// add(sum, 1ll * ((p & 1) ? mod - 1 : 1) * ivf[cnt - p] % mod * ivf[p] % mod * ivf[k - p] % mod * ivf[n * m - (cnt - p) - k] % mod);
// }
add(ans, 1ll * f[cnt] * fac[cnt] % mod * fac[n * m - cnt] % mod *
binom(n, x) % mod * binom(m, y) % mod * (((x + y) & 1) ? mod - 1 : 1) % mod);
}
rep (i, 1, n + m) ans = 1ll * ans * iv2 % mod;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 2ms
memory: 11944kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 1ms
memory: 11788kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 1ms
memory: 11872kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 1ms
memory: 11884kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 5ms
memory: 11924kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 5ms
memory: 11876kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 3ms
memory: 11868kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 2ms
memory: 11872kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 83ms
memory: 14704kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 94ms
memory: 16920kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 97ms
memory: 14876kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 410ms
memory: 26068kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 401ms
memory: 29212kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 193ms
memory: 17192kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 199ms
memory: 19944kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 418ms
memory: 24544kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 418ms
memory: 29204kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 438ms
memory: 25904kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 437ms
memory: 27728kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 168ms
memory: 18024kb
input:
501 501 251001
output:
1
result:
ok single line: '1'