QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369467 | #3082. Ascending Matrix | yaoxi_std | AC ✓ | 584ms | 14044kb | C++14 | 3.9kb | 2024-03-28 10:56:47 | 2024-03-28 10:56:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 1e3 + 10, mod = 998244353;
int n, m, k, px, py, pval, a[N][N], f[N], g[N], h[N], val[N], fac[N], ifac[N];
pair<int, int> b[N][N];
inline void add(int& x, int y) { x += y, x >= mod && (x -= mod); }
inline void sub(int& x, int y) { x -= y, x < 0 && (x += mod); }
inline int sum(int x, int y) { return x += y, x >= mod ? x - mod : x; }
inline int dif(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline int neg(int x) { return x ? mod - x : 0; }
inline int bin(int n, int m) {
if (n < m || m < 0) return 0;
return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int qpow(int x, int y) {
int ret = 1;
for (; y; y >>= 1, x = (ll)x * x % mod)
if (y & 1) ret = (ll)ret * x % mod;
return ret;
}
pair<int,int> get_dp(int n, int m, int bx, int by) {
if (n < 0 || m < 0) return make_pair(0, 0);
static int dp[N][N][2];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j][0] = dp[i][j][1] = 0;
if (!i && !j) dp[i][j][0] = dp[i][j][1] = 1;
if (i) {
add(dp[i][j][0], dp[i - 1][j][0]);
add(dp[i][j][1], dp[i - 1][j][1]);
}
if (j) {
add(dp[i][j][0], dp[i][j - 1][0]);
add(dp[i][j][1], dp[i][j - 1][1]);
}
if (i > bx && j < by) dp[i][j][0] = 0;
if (i < bx && j > by) dp[i][j][1] = 0;
if (i == bx && j == by) dp[i][j][0] = dp[i][j][1] = 0;
}
}
return make_pair(dp[n][m][0], dp[n][m][1]);
}
int det(int n) {
int prd = 1;
for (int i = 1; i <= n; ++i) {
int p = i;
for (int j = i; j <= n; ++j) if (a[j][i]) { p = j; break; }
if (p != i) {
prd = neg(prd);
for (int j = i; j <= n; ++j) swap(a[i][j], a[p][j]);
}
if (!a[i][i]) return 0;
prd = (ll)prd * a[i][i] % mod;
int inv = qpow(a[i][i], mod - 2);
for (int j = i; j <= n; ++j) a[i][j] = (ll)a[i][j] * inv % mod;
for (int j = i + 1; j <= n; ++j) {
int tmp = a[j][i];
for (int k = i; k <= n; ++k) sub(a[j][k], (ll)a[i][k] * tmp % mod);
}
}
return prd;
}
bool Med;
int main() {
// debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k >> px >> py >> pval, --pval;
fac[0] = ifac[0] = ifac[1] = 1;
for (int i = 1; i < N; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
for (int i= 2; i < N; ++i) ifac[i] = (ll)ifac[mod % i] * (mod - mod / i) % mod;
for (int i = 2; i < N; ++i) ifac[i] = (ll)ifac[i - 1] * ifac[i] % mod;
for (int i = 1; i < k; ++i) {
for (int j = 1; j < k; ++j) {
int x1 = n + i - 1, y1 = i - 1;
int x2 = j - 1, y2 = m + j - 1;
int tx = px + pval - 1, ty = py + pval - 1;
b[i][j] = get_dp(x1 - x2, y2 - y1, x1 - tx, ty - y1);
}
}
g[0] = 1;
for (int x = 1; x <= k; ++x) {
for (int i = x; i >= 1; --i) g[i] = (g[i - 1] + (ll)g[i] * neg(x)) % mod;
g[0] = (ll)g[0] * neg(x) % mod;
}
for (int x = 1; x <= k; ++x) {
for (int i = 1; i < k; ++i) {
for (int j = 1; j < k; ++j) {
a[i][j] = ((ll)b[i][j].second * x + b[i][j].first) % mod;
}
}
int y = det(k - 1), prd = 1;
for (int i = 1; i <= k; ++i) if (i != x) prd = (ll)prd * dif(x, i) % mod;
prd = (ll)y * qpow(prd, mod - 2) % mod;
for (int i = k - 1; ~i; --i)
h[i] = (g[i + 1] + (ll)h[i + 1] * x) % mod;
for (int i = 0; i < k; ++i)
f[i] = (f[i] + (ll)prd * h[i]) % mod;
}
cout << f[pval] << '\n';
return 0;
}
/*
g++ -std=c++14 -O2 -o qoj-3082 qoj-3082.cpp -Wall -Wextra
-Wshadow -fsanitize=address,undefined -g
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 97ms
memory: 9932kb
input:
148 129 48 144 105 13
output:
467058311
result:
ok single line: '467058311'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7712kb
input:
57 48 11 56 9 1
output:
951177245
result:
ok single line: '951177245'
Test #3:
score: 0
Accepted
time: 213ms
memory: 12128kb
input:
121 146 72 117 72 25
output:
284798523
result:
ok single line: '284798523'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
66 142 11 51 124 4
output:
542285716
result:
ok single line: '542285716'
Test #5:
score: 0
Accepted
time: 144ms
memory: 12240kb
input:
45 127 98 3 31 80
output:
116902187
result:
ok single line: '116902187'
Test #6:
score: 0
Accepted
time: 120ms
memory: 12000kb
input:
125 199 45 51 91 21
output:
715355617
result:
ok single line: '715355617'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7824kb
input:
41 153 6 6 147 2
output:
190519561
result:
ok single line: '190519561'
Test #8:
score: 0
Accepted
time: 136ms
memory: 8096kb
input:
112 108 69 99 29 47
output:
481688971
result:
ok single line: '481688971'
Test #9:
score: 0
Accepted
time: 284ms
memory: 8204kb
input:
138 99 94 73 43 73
output:
667469005
result:
ok single line: '667469005'
Test #10:
score: 0
Accepted
time: 16ms
memory: 7784kb
input:
143 147 18 24 141 9
output:
763965115
result:
ok single line: '763965115'
Test #11:
score: 0
Accepted
time: 142ms
memory: 12276kb
input:
99 63 97 78 51 66
output:
130195301
result:
ok single line: '130195301'
Test #12:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
103 23 10 25 7 4
output:
674555733
result:
ok single line: '674555733'
Test #13:
score: 0
Accepted
time: 109ms
memory: 11972kb
input:
137 194 42 125 104 17
output:
416667361
result:
ok single line: '416667361'
Test #14:
score: 0
Accepted
time: 7ms
memory: 9872kb
input:
191 13 37 42 2 21
output:
530754407
result:
ok single line: '530754407'
Test #15:
score: 0
Accepted
time: 41ms
memory: 11976kb
input:
195 33 53 101 29 32
output:
851306824
result:
ok single line: '851306824'
Test #16:
score: 0
Accepted
time: 3ms
memory: 7804kb
input:
84 173 8 70 70 6
output:
25135799
result:
ok single line: '25135799'
Test #17:
score: 0
Accepted
time: 13ms
memory: 7888kb
input:
39 53 49 37 6 9
output:
640044940
result:
ok single line: '640044940'
Test #18:
score: 0
Accepted
time: 189ms
memory: 12008kb
input:
135 129 68 134 86 16
output:
910022919
result:
ok single line: '910022919'
Test #19:
score: 0
Accepted
time: 35ms
memory: 8000kb
input:
62 74 56 28 12 46
output:
774987233
result:
ok single line: '774987233'
Test #20:
score: 0
Accepted
time: 180ms
memory: 12064kb
input:
87 135 81 27 44 58
output:
629485683
result:
ok single line: '629485683'
Test #21:
score: 0
Accepted
time: 133ms
memory: 9964kb
input:
148 199 44 79 81 40
output:
369408819
result:
ok single line: '369408819'
Test #22:
score: 0
Accepted
time: 0ms
memory: 7736kb
input:
18 195 5 17 151 5
output:
198068951
result:
ok single line: '198068951'
Test #23:
score: 0
Accepted
time: 360ms
memory: 10188kb
input:
200 137 75 67 65 74
output:
864017958
result:
ok single line: '864017958'
Test #24:
score: 0
Accepted
time: 197ms
memory: 10072kb
input:
171 162 56 113 97 30
output:
255341800
result:
ok single line: '255341800'
Test #25:
score: 0
Accepted
time: 7ms
memory: 7908kb
input:
8 134 38 1 93 10
output:
282048962
result:
ok single line: '282048962'
Test #26:
score: 0
Accepted
time: 45ms
memory: 8256kb
input:
13 55 93 3 25 40
output:
852404927
result:
ok single line: '852404927'
Test #27:
score: 0
Accepted
time: 97ms
memory: 11896kb
input:
169 157 42 77 108 39
output:
595819517
result:
ok single line: '595819517'
Test #28:
score: 0
Accepted
time: 161ms
memory: 8088kb
input:
41 199 87 18 82 58
output:
698977796
result:
ok single line: '698977796'
Test #29:
score: 0
Accepted
time: 97ms
memory: 9956kb
input:
190 68 57 188 59 15
output:
46174623
result:
ok single line: '46174623'
Test #30:
score: 0
Accepted
time: 59ms
memory: 12144kb
input:
90 52 71 39 41 23
output:
417181087
result:
ok single line: '417181087'
Test #31:
score: 0
Accepted
time: 153ms
memory: 12112kb
input:
108 76 89 55 40 13
output:
210578964
result:
ok single line: '210578964'
Test #32:
score: 0
Accepted
time: 52ms
memory: 7768kb
input:
166 191 27 102 30 11
output:
365224233
result:
ok single line: '365224233'
Test #33:
score: 0
Accepted
time: 1ms
memory: 7728kb
input:
41 166 4 10 49 2
output:
245797147
result:
ok single line: '245797147'
Test #34:
score: 0
Accepted
time: 259ms
memory: 10116kb
input:
135 128 79 44 16 6
output:
203896980
result:
ok single line: '203896980'
Test #35:
score: 0
Accepted
time: 301ms
memory: 12116kb
input:
101 193 79 43 65 75
output:
27637457
result:
ok single line: '27637457'
Test #36:
score: 0
Accepted
time: 45ms
memory: 12088kb
input:
88 81 53 35 54 47
output:
950708598
result:
ok single line: '950708598'
Test #37:
score: 0
Accepted
time: 8ms
memory: 9880kb
input:
87 40 28 37 8 8
output:
817953396
result:
ok single line: '817953396'
Test #38:
score: 0
Accepted
time: 542ms
memory: 10208kb
input:
193 136 94 12 94 23
output:
145619900
result:
ok single line: '145619900'
Test #39:
score: 0
Accepted
time: 178ms
memory: 8012kb
input:
90 183 67 8 171 26
output:
899333159
result:
ok single line: '899333159'
Test #40:
score: 0
Accepted
time: 45ms
memory: 7904kb
input:
107 178 32 24 103 12
output:
82019799
result:
ok single line: '82019799'
Test #41:
score: 0
Accepted
time: 35ms
memory: 11996kb
input:
160 23 61 60 17 3
output:
350971684
result:
ok single line: '350971684'
Test #42:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
100 176 10 54 58 4
output:
978823166
result:
ok single line: '978823166'
Test #43:
score: 0
Accepted
time: 131ms
memory: 9892kb
input:
181 183 42 7 91 41
output:
690262327
result:
ok single line: '690262327'
Test #44:
score: 0
Accepted
time: 69ms
memory: 12004kb
input:
105 131 47 53 68 33
output:
806603020
result:
ok single line: '806603020'
Test #45:
score: 0
Accepted
time: 51ms
memory: 14044kb
input:
51 10 100 1 5 73
output:
341852925
result:
ok single line: '341852925'
Test #46:
score: 0
Accepted
time: 227ms
memory: 8048kb
input:
87 198 73 75 109 72
output:
741170008
result:
ok single line: '741170008'
Test #47:
score: 0
Accepted
time: 2ms
memory: 7716kb
input:
25 158 13 22 1 1
output:
237363061
result:
ok single line: '237363061'
Test #48:
score: 0
Accepted
time: 87ms
memory: 7988kb
input:
64 112 71 28 109 10
output:
350168232
result:
ok single line: '350168232'
Test #49:
score: 0
Accepted
time: 171ms
memory: 9952kb
input:
143 191 52 10 98 10
output:
71885894
result:
ok single line: '71885894'
Test #50:
score: 0
Accepted
time: 10ms
memory: 7904kb
input:
30 130 36 22 85 6
output:
909971212
result:
ok single line: '909971212'
Test #51:
score: 0
Accepted
time: 72ms
memory: 9960kb
input:
154 136 38 34 109 15
output:
655764791
result:
ok single line: '655764791'
Test #52:
score: 0
Accepted
time: 0ms
memory: 11928kb
input:
13 112 7 9 55 1
output:
623849663
result:
ok single line: '623849663'
Test #53:
score: 0
Accepted
time: 73ms
memory: 8012kb
input:
137 103 47 56 77 35
output:
43033659
result:
ok single line: '43033659'
Test #54:
score: 0
Accepted
time: 4ms
memory: 7820kb
input:
40 17 37 11 7 15
output:
803046927
result:
ok single line: '803046927'
Test #55:
score: 0
Accepted
time: 27ms
memory: 7972kb
input:
166 14 58 49 1 26
output:
664593299
result:
ok single line: '664593299'
Test #56:
score: 0
Accepted
time: 6ms
memory: 7772kb
input:
88 195 15 10 120 5
output:
925522664
result:
ok single line: '925522664'
Test #57:
score: 0
Accepted
time: 584ms
memory: 12312kb
input:
164 166 96 161 138 32
output:
111053370
result:
ok single line: '111053370'
Test #58:
score: 0
Accepted
time: 419ms
memory: 14036kb
input:
145 135 94 68 83 9
output:
394110532
result:
ok single line: '394110532'
Test #59:
score: 0
Accepted
time: 247ms
memory: 7952kb
input:
154 173 63 5 77 51
output:
540440686
result:
ok single line: '540440686'
Test #60:
score: 0
Accepted
time: 5ms
memory: 7832kb
input:
20 91 30 20 83 17
output:
961395776
result:
ok single line: '961395776'
Test #61:
score: 0
Accepted
time: 0ms
memory: 9884kb
input:
144 39 13 77 9 5
output:
99731481
result:
ok single line: '99731481'
Test #62:
score: 0
Accepted
time: 216ms
memory: 8140kb
input:
87 152 83 4 59 81
output:
139490896
result:
ok single line: '139490896'
Test #63:
score: 0
Accepted
time: 428ms
memory: 14028kb
input:
171 135 89 114 124 10
output:
736020363
result:
ok single line: '736020363'
Test #64:
score: 0
Accepted
time: 97ms
memory: 8284kb
input:
82 41 99 66 6 5
output:
882042301
result:
ok single line: '882042301'
Test #65:
score: 0
Accepted
time: 8ms
memory: 9940kb
input:
33 114 28 11 73 11
output:
653378940
result:
ok single line: '653378940'
Test #66:
score: 0
Accepted
time: 0ms
memory: 9804kb
input:
180 73 10 43 63 9
output:
170492767
result:
ok single line: '170492767'
Test #67:
score: 0
Accepted
time: 62ms
memory: 8068kb
input:
33 185 63 19 107 7
output:
907253908
result:
ok single line: '907253908'
Test #68:
score: 0
Accepted
time: 4ms
memory: 11780kb
input:
69 90 22 34 31 3
output:
137223161
result:
ok single line: '137223161'
Test #69:
score: 0
Accepted
time: 19ms
memory: 12080kb
input:
42 45 60 29 38 36
output:
99908563
result:
ok single line: '99908563'
Test #70:
score: 0
Accepted
time: 30ms
memory: 7812kb
input:
69 158 34 56 39 17
output:
681472254
result:
ok single line: '681472254'
Test #71:
score: 0
Accepted
time: 81ms
memory: 13972kb
input:
66 69 84 5 8 41
output:
277373736
result:
ok single line: '277373736'
Test #72:
score: 0
Accepted
time: 59ms
memory: 10024kb
input:
168 31 68 66 4 21
output:
528816013
result:
ok single line: '528816013'
Test #73:
score: 0
Accepted
time: 60ms
memory: 10108kb
input:
65 33 94 2 30 76
output:
331224077
result:
ok single line: '331224077'
Test #74:
score: 0
Accepted
time: 4ms
memory: 7804kb
input:
84 111 12 28 106 12
output:
95279945
result:
ok single line: '95279945'
Test #75:
score: 0
Accepted
time: 128ms
memory: 8064kb
input:
102 77 83 95 62 51
output:
773914979
result:
ok single line: '773914979'
Test #76:
score: 0
Accepted
time: 221ms
memory: 10104kb
input:
113 144 76 24 68 13
output:
845242590
result:
ok single line: '845242590'
Test #77:
score: 0
Accepted
time: 0ms
memory: 7704kb
input:
45 24 9 10 2 5
output:
71790514
result:
ok single line: '71790514'
Test #78:
score: 0
Accepted
time: 134ms
memory: 8032kb
input:
158 98 61 86 50 29
output:
123475901
result:
ok single line: '123475901'
Test #79:
score: 0
Accepted
time: 11ms
memory: 7748kb
input:
118 52 27 11 23 21
output:
489202572
result:
ok single line: '489202572'
Test #80:
score: 0
Accepted
time: 48ms
memory: 9916kb
input:
122 148 35 112 17 17
output:
856169627
result:
ok single line: '856169627'
Test #81:
score: 0
Accepted
time: 8ms
memory: 7792kb
input:
135 114 15 20 43 9
output:
873320383
result:
ok single line: '873320383'
Test #82:
score: 0
Accepted
time: 109ms
memory: 8104kb
input:
89 70 84 70 12 18
output:
302990320
result:
ok single line: '302990320'
Test #83:
score: 0
Accepted
time: 21ms
memory: 13920kb
input:
15 68 67 5 51 66
output:
980298686
result:
ok single line: '980298686'
Test #84:
score: 0
Accepted
time: 14ms
memory: 8140kb
input:
50 2 73 40 2 8
output:
550497760
result:
ok single line: '550497760'
Test #85:
score: 0
Accepted
time: 171ms
memory: 13860kb
input:
117 88 83 93 1 50
output:
645491986
result:
ok single line: '645491986'
Test #86:
score: 0
Accepted
time: 55ms
memory: 7916kb
input:
45 173 54 34 93 3
output:
330947509
result:
ok single line: '330947509'
Test #87:
score: 0
Accepted
time: 2ms
memory: 7796kb
input:
39 10 22 34 6 20
output:
184357429
result:
ok single line: '184357429'
Test #88:
score: 0
Accepted
time: 26ms
memory: 11828kb
input:
58 27 71 55 19 22
output:
201813851
result:
ok single line: '201813851'
Test #89:
score: 0
Accepted
time: 24ms
memory: 12072kb
input:
123 57 40 14 38 23
output:
891805630
result:
ok single line: '891805630'
Test #90:
score: 0
Accepted
time: 65ms
memory: 8032kb
input:
84 64 70 12 2 23
output:
351372969
result:
ok single line: '351372969'
Test #91:
score: 0
Accepted
time: 97ms
memory: 8056kb
input:
46 160 72 21 146 9
output:
625614461
result:
ok single line: '625614461'
Test #92:
score: 0
Accepted
time: 37ms
memory: 12128kb
input:
45 99 57 25 40 4
output:
498175745
result:
ok single line: '498175745'
Test #93:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
15 21 12 14 6 3
output:
727195216
result:
ok single line: '727195216'
Test #94:
score: 0
Accepted
time: 28ms
memory: 9848kb
input:
154 77 32 73 62 15
output:
513610382
result:
ok single line: '513610382'
Test #95:
score: 0
Accepted
time: 10ms
memory: 9884kb
input:
165 97 16 158 69 11
output:
308621770
result:
ok single line: '308621770'
Test #96:
score: 0
Accepted
time: 419ms
memory: 13968kb
input:
146 128 97 132 24 10
output:
751957330
result:
ok single line: '751957330'
Test #97:
score: 0
Accepted
time: 7ms
memory: 7860kb
input:
49 39 35 2 10 14
output:
338882448
result:
ok single line: '338882448'
Test #98:
score: 0
Accepted
time: 14ms
memory: 10028kb
input:
73 1 73 35 1 44
output:
126891463
result:
ok single line: '126891463'
Test #99:
score: 0
Accepted
time: 44ms
memory: 7976kb
input:
69 82 59 1 73 1
output:
436743471
result:
ok single line: '436743471'
Test #100:
score: 0
Accepted
time: 22ms
memory: 12032kb
input:
88 86 40 19 77 4
output:
758000538
result:
ok single line: '758000538'