QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #739448 | #9611. 木桶效应 | I_be_wanna | 100 ✓ | 617ms | 13592kb | C++14 | 7.3kb | 2024-11-12 21:47:08 | 2024-11-12 21:47:09 |
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
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 = 55;
int n, m, q;
int fc[N], ifc[N];
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;
}
}
IL int C (int n, int m) {
return n < m || m < 0 ? 0 : (LL)fc[n] * ifc[m] % P * ifc[n - m] % P;
}
namespace F1 {
int f[N][N], p[N][N];
void main () {
L (i, 0, n) {
L (j, 0, i) {
p[i][j] = qpow(fc[i] * (LL)ifc[j] % P, m);
}
}
f[n + 1][0] = 1;
R (i, n, 1) {
L (k, 0, n - i) {
int x = f[i + 1][k];
if (x) {
L (j, k, n - i + 1) {
f[i][j] = (f[i][j] + (LL)x * p[n - i + 1 - k][n - i + 1 - j] % P * C(n - k, j - k)) % P;
}
}
}
}
cout << f[1][n] << '\n';
}
}
namespace F2 {
int g[12][N][1 << 10];
vector<pair<int, int>> lis[12];
int f[N][N][1 << 10], _f[1 << 10];
int cnt, l;
unordered_map<int, int> idx, ids;
int pw[N], ipw[N];
int pc[1 << 10], mn[1 << 10];
void main () {
L (i, 0, q - 1) {
int x, y, w;
cin >> x >> y >> w;
if (!ids.count(y)) {
ids[y] = l++;
}
if (!idx.count(x)) {
idx[x] = ++cnt;
}
lis[idx[x]].eb(ids[y], w);
}
L (i, 0, n) {
pw[i] = qpow(fc[i], m - cnt);
ipw[i] = qpow(ifc[i], m - cnt);
}
mn[0] = n + 1;
L (i, 0, l - 1) {
mn[1 << i] = n + 1;
}
L (i, 1, cnt) {
for (auto [x, y] : lis[i]) {
mn[1 << x] = min(mn[1 << x], y);
}
}
L (i, 1, (1 << l) - 1) {
mn[i] = min(mn[i & (i - 1)], mn[i & -i]);
}
L (i, 1, cnt) {
R (b, n, 1) {
L (s, 0, (1 << l) - 1) {
g[i][b][s] = g[i][b + 1][s];
for (auto [x, y] : lis[i]) {
g[i][b][s] += (~s >> x & 1) && (b == y);
}
}
}
}
L (i, 1, (1 << l) - 1) {
pc[i] = pc[i >> 1] + (i & 1);
}
f[n + 1][0][0] = 1;
R (b, n, 1) {
L (i, 0, n - l) {
L (s, 0, (1 << l) - 1) {
LL x = f[b + 1][i][s];
if (x) {
x = x * pw[n - b + 1 - i - pc[s]] % P;
L (k, 1, cnt) {
x = x * fc[n - b + 1 - i - pc[s] - g[k][b][s]] % P;
}
}
_f[s] = x;
}
for (int ph = 2; ph <= (1 << l); ph <<= 1) {
int p = ph >> 1;
for (int j = 0; j < (1 << l); j += ph) {
L (k, 0, p - 1) {
_f[j + k + p] = (_f[j + k + p] + _f[j + k]) % P;
}
}
}
L (j, i, n - l) {
L (t, 0, (1 << l) - 1) {
if (j + pc[t] <= n - b + 1 && mn[t] >= b) {
LL x = _f[t] * (LL)ipw[n - b + 1 - j - pc[t]] % P * C(n - l - i, j - i) % P;
if (x) {
L (k, 1, cnt) {
int pp = n - b + 1 - j - pc[t] - g[k][b][t];
if (pp < 0) {
x = 0;
break;
}
x = x * ifc[pp] % P;
}
}
f[b][j][t] = (f[b][j][t] + x) % P;
}
}
}
}
}
cout << f[1][n - l][(1 << l) - 1] << '\n';
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
init(n);
if (q == 0) {
F1::main();
} else {
F2::main();
}
}
/*#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
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 = 55;
int n, m, q;
int fc[N], ifc[N];
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;
}
}
IL int C (int n, int m) {
return n < m || m < 0 ? 0 : (LL)fc[n] * ifc[m] % P * ifc[n - m] % P;
}
namespace F1 {
int f[N][N], p[N][N];
void main () {
L (i, 0, n) {
L (j, 0, i) {
p[i][j] = qpow(fc[i] * (LL)ifc[j] % P, m);
}
}
f[n + 1][0] = 1;
R (i, n, 1) {
L (k, 0, n - i) {
int x = f[i + 1][k];
if (x) {
L (j, k, n - i + 1) {
f[i][j] = (f[i][j] + (LL)x * p[n - i + 1 - k][n - i + 1 - j] % P * C(n - k, j - k)) % P;
}
}
}
}
cout << f[1][n] << '\n';
}
}
namespace F2 {
int g[12][N][1 << 10];
vector<pair<int, int>> lis[12];
int f[N][N][1 << 10], _f[1 << 10];
int cnt, l;
unordered_map<int, int> idx, ids;
int pw[N], ipw[N];
int pc[1 << 10], mn[1 << 10];
void main () {
L (i, 0, q - 1) {
int x, y, w;
cin >> x >> y >> w;
if (!ids.count(y)) {
ids[y] = l++;
}
if (!idx.count(x)) {
idx[x] = ++cnt;
}
lis[idx[x]].eb(ids[y], w);
}
L (i, 0, n) {
pw[i] = qpow(fc[i], m - cnt);
ipw[i] = qpow(ifc[i], m - cnt);
}
mn[0] = n + 1;
L (i, 0, l - 1) {
mn[1 << i] = n + 1;
}
L (i, 1, cnt) {
for (auto [x, y] : lis[i]) {
mn[1 << x] = min(mn[1 << x], y);
}
}
L (i, 1, (1 << l) - 1) {
mn[i] = min(mn[i & (i - 1)], mn[i & -i]);
}
L (i, 1, cnt) {
R (b, n, 1) {
L (s, 0, (1 << l) - 1) {
g[i][b][s] = g[i][b + 1][s];
for (auto [x, y] : lis[i]) {
g[i][b][s] += (~s >> x & 1) && (b == y);
}
}
}
}
L (i, 1, (1 << l) - 1) {
pc[i] = pc[i >> 1] + (i & 1);
}
f[n + 1][0][0] = 1;
R (b, n, 1) {
L (i, 0, n - l) {
L (s, 0, (1 << l) - 1) {
LL x = f[b + 1][i][s];
if (x) {
x = x * pw[n - b + 1 - i - pc[s]] % P;
L (k, 1, cnt) {
x = x * fc[n - b + 1 - i - pc[s] - g[k][b][s]] % P;
}
}
_f[s] = x;
}
for (int ph = 2; ph <= (1 << l); ph <<= 1) {
int p = ph >> 1;
for (int j = 0; j < (1 << l); j += ph) {
L (k, 0, p - 1) {
_f[j + k + p] = (_f[j + k + p] + _f[j + k]) % P;
}
}
}
L (j, i, n - l) {
L (t, 0, (1 << l) - 1) {
if (j + pc[t] <= n - b + 1 && mn[t] >= b) {
LL x = _f[t] * (LL)ipw[n - b + 1 - j - pc[t]] % P * C(n - l - i, j - i) % P;
if (x) {
L (k, 1, cnt) {
F2::main();
}
}*/
详细
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 0ms
memory: 5624kb
input:
5 3 0
output:
21412920
result:
ok single line: '21412920'
Test #2:
score: 4
Accepted
time: 1ms
memory: 7684kb
input:
5 3 2 3 4 4 2 5 3
output:
847674
result:
ok single line: '847674'
Test #3:
score: 4
Accepted
time: 1ms
memory: 7936kb
input:
5 3 3 3 5 5 1 2 5 2 5 3
output:
168780
result:
ok single line: '168780'
Subtask #2:
score: 8
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 8
Accepted
time: 1ms
memory: 5624kb
input:
7 3 0
output:
160221085
result:
ok single line: '160221085'
Test #5:
score: 8
Accepted
time: 1ms
memory: 7848kb
input:
7 3 2 1 1 5 1 6 2
output:
598007855
result:
ok single line: '598007855'
Test #6:
score: 8
Accepted
time: 1ms
memory: 8060kb
input:
7 3 3 1 1 5 2 6 3 2 1 7
output:
950880222
result:
ok single line: '950880222'
Subtask #3:
score: 8
Accepted
Test #7:
score: 8
Accepted
time: 1ms
memory: 5896kb
input:
50 1 0
output:
263941435
result:
ok single line: '263941435'
Test #8:
score: 8
Accepted
time: 1ms
memory: 5640kb
input:
43 2 0
output:
136378346
result:
ok single line: '136378346'
Test #9:
score: 8
Accepted
time: 1ms
memory: 5584kb
input:
50 2 0
output:
489087596
result:
ok single line: '489087596'
Subtask #4:
score: 12
Accepted
Dependency #3:
100%
Accepted
Test #10:
score: 12
Accepted
time: 1ms
memory: 5704kb
input:
50 292247015 0
output:
226872193
result:
ok single line: '226872193'
Test #11:
score: 12
Accepted
time: 1ms
memory: 7900kb
input:
50 873009728 0
output:
63648791
result:
ok single line: '63648791'
Subtask #5:
score: 16
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #12:
score: 16
Accepted
time: 2ms
memory: 8644kb
input:
20 728836785 5 248289571 15 16 439110385 8 15 339467267 12 7 585491339 7 9 605518440 4 1
output:
761275883
result:
ok single line: '761275883'
Test #13:
score: 16
Accepted
time: 0ms
memory: 8988kb
input:
20 288197925 5 31379347 9 1 222153278 1 1 24531748 20 1 106427339 18 1 212338331 17 1
output:
877851586
result:
ok single line: '877851586'
Test #14:
score: 16
Accepted
time: 0ms
memory: 8476kb
input:
20 880439688 5 563540321 17 20 395236367 3 20 300712779 6 20 121406689 18 20 25890496 9 20
output:
186649553
result:
ok single line: '186649553'
Test #15:
score: 16
Accepted
time: 2ms
memory: 8572kb
input:
20 311402369 5 311293636 14 13 306211116 19 19 36858994 5 11 36858994 19 10 306211116 14 18
output:
415461922
result:
ok single line: '415461922'
Test #16:
score: 16
Accepted
time: 2ms
memory: 8572kb
input:
20 98953332 5 1075868 12 5 31161114 8 12 46790018 9 10 39214697 15 7 46790018 8 8
output:
204149614
result:
ok single line: '204149614'
Subtask #6:
score: 12
Accepted
Dependency #5:
100%
Accepted
Test #17:
score: 12
Accepted
time: 11ms
memory: 11956kb
input:
50 915702052 5 541920465 39 16 833447607 49 14 326677362 14 34 412319566 10 36 206682128 46 28
output:
783441394
result:
ok single line: '783441394'
Test #18:
score: 12
Accepted
time: 3ms
memory: 11284kb
input:
50 47879239 5 30666754 20 1 23945845 17 1 27229141 25 1 40551703 9 1 15723198 18 1
output:
546399382
result:
ok single line: '546399382'
Test #19:
score: 12
Accepted
time: 17ms
memory: 11072kb
input:
50 334191703 5 167838076 19 50 95127599 33 50 221030062 4 50 89223523 36 50 40736662 39 50
output:
242104112
result:
ok single line: '242104112'
Test #20:
score: 12
Accepted
time: 6ms
memory: 11040kb
input:
50 33538004 5 1341436 40 26 19132404 4 13 22271562 24 25 19132404 40 18 19132404 24 38
output:
509216038
result:
ok single line: '509216038'
Test #21:
score: 12
Accepted
time: 4ms
memory: 11564kb
input:
50 453197583 5 304895210 17 41 450727109 33 20 129855576 4 24 214262208 12 46 214262208 4 27
output:
929330226
result:
ok single line: '929330226'
Subtask #7:
score: 20
Accepted
Dependency #6:
100%
Accepted
Test #22:
score: 20
Accepted
time: 59ms
memory: 11920kb
input:
50 733592974 7 204969642 20 32 532101473 38 22 428067108 29 19 699479674 23 35 403248947 11 33 523610998 39 50 207894041 37 47
output:
878602112
result:
ok single line: '878602112'
Test #23:
score: 20
Accepted
time: 12ms
memory: 12264kb
input:
50 363989184 7 275675456 32 1 14440487 41 1 84675645 18 1 112753584 7 1 259289962 30 1 244964889 42 1 34667760 27 1
output:
125183718
result:
ok single line: '125183718'
Test #24:
score: 20
Accepted
time: 55ms
memory: 12732kb
input:
50 987882639 7 17913003 22 50 440453368 26 50 849090802 8 50 106136773 13 50 491841612 34 50 131376512 15 50 231961452 39 50
output:
573542486
result:
ok single line: '573542486'
Test #25:
score: 20
Accepted
time: 3ms
memory: 12820kb
input:
50 739368354 7 163377222 20 27 192827369 29 10 688310083 50 13 20398047 27 45 688310083 29 11 192827369 20 5 688310083 27 27
output:
528550901
result:
ok single line: '528550901'
Test #26:
score: 20
Accepted
time: 8ms
memory: 12856kb
input:
50 691852384 7 552436456 27 11 103126750 8 13 122888842 49 34 306609066 7 11 553011271 38 32 553011271 27 47 553011271 49 50
output:
407673475
result:
ok single line: '407673475'
Test #27:
score: 20
Accepted
time: 13ms
memory: 12716kb
input:
50 828246844 7 528561184 35 4 15522388 43 35 679004541 17 20 161133582 6 20 289045078 32 49 705209075 24 38 705209075 17 44
output:
734432988
result:
ok single line: '734432988'
Subtask #8:
score: 12
Accepted
Dependency #7:
100%
Accepted
Test #28:
score: 12
Accepted
time: 210ms
memory: 13328kb
input:
50 818455715 9 460012830 5 33 118588510 47 47 281020207 23 25 175303600 1 18 234157803 48 32 256460906 19 46 287657461 24 13 81772046 14 22 114821805 44 41
output:
863394340
result:
ok single line: '863394340'
Test #29:
score: 12
Accepted
time: 41ms
memory: 12496kb
input:
50 24969517 9 23565097 13 1 11005666 43 1 21727790 47 1 12763778 6 1 6881701 34 1 2985794 23 1 13971040 15 1 13187518 29 1 1995154 12 1
output:
755357189
result:
ok single line: '755357189'
Test #30:
score: 12
Accepted
time: 291ms
memory: 13256kb
input:
50 429772980 9 414497820 4 50 141139445 19 50 407732495 7 50 83785413 1 50 164351908 8 50 213988430 26 50 52240611 50 50 352159955 27 50 279326344 29 50
output:
247413078
result:
ok single line: '247413078'
Test #31:
score: 12
Accepted
time: 15ms
memory: 11952kb
input:
50 919810726 9 403069670 48 3 193931638 39 28 821686776 22 11 432351038 8 49 466123383 14 34 254851369 2 48 193931638 48 38 821686776 8 19 254851369 8 20
output:
481094724
result:
ok single line: '481094724'
Test #32:
score: 12
Accepted
time: 22ms
memory: 13060kb
input:
50 619619808 9 140356219 25 31 289966305 18 15 308904151 23 44 530131662 15 2 174186843 35 5 452736627 42 7 12231110 21 2 308904151 18 33 140356219 18 30
output:
194056785
result:
ok single line: '194056785'
Test #33:
score: 12
Accepted
time: 40ms
memory: 11656kb
input:
50 405638475 9 189173757 25 33 313860932 22 8 196599730 26 6 273814431 3 2 52701532 15 14 335951766 19 3 313077524 29 13 349363426 7 15 313860932 19 19
output:
435209021
result:
ok single line: '435209021'
Subtask #9:
score: 8
Accepted
Dependency #8:
100%
Accepted
Test #34:
score: 8
Accepted
time: 259ms
memory: 12180kb
input:
50 946059042 10 160844820 11 40 246397981 49 28 373026730 1 18 602144414 9 9 284028279 39 44 22155194 16 2 851925494 6 17 862159117 27 32 773018252 10 20 462257810 48 19
output:
680391855
result:
ok single line: '680391855'
Test #35:
score: 8
Accepted
time: 91ms
memory: 13592kb
input:
50 260661857 10 70899239 47 1 248286199 34 1 49459370 23 1 110741847 3 1 13147285 19 1 75609139 10 1 16001621 49 1 258636033 17 1 41404092 36 1 259336018 9 1
output:
621578303
result:
ok single line: '621578303'
Test #36:
score: 8
Accepted
time: 617ms
memory: 12696kb
input:
50 444766827 10 138606634 2 50 356874907 48 50 186818234 44 50 328471606 8 50 57922803 45 50 442175507 50 50 45412871 41 50 111164719 24 50 278665393 39 50 49548102 15 50
output:
476500313
result:
ok single line: '476500313'
Test #37:
score: 8
Accepted
time: 21ms
memory: 12156kb
input:
50 471185620 10 330350191 32 46 19091103 17 9 383913632 38 25 125638511 4 13 227803510 12 49 140314389 27 34 97824926 22 46 19091103 27 16 140314389 38 4 97824926 12 1
output:
746959227
result:
ok single line: '746959227'
Test #38:
score: 8
Accepted
time: 85ms
memory: 13476kb
input:
50 534235345 10 505481965 11 39 325061903 12 35 443938537 40 20 144968487 29 31 292692014 18 39 423914803 14 36 221863124 46 41 413488879 5 39 413488879 14 5 325061903 11 42
output:
83413094
result:
ok single line: '83413094'
Test #39:
score: 8
Accepted
time: 122ms
memory: 12304kb
input:
50 268783055 10 164040236 5 3 77416439 15 8 215664484 32 34 84807773 8 44 242418459 20 43 132116147 31 13 11369559 50 23 264864429 6 42 153908131 3 27 132116147 20 50
output:
858392519
result:
ok single line: '858392519'
Test #40:
score: 8
Accepted
time: 8ms
memory: 12224kb
input:
50 680178330 10 381317639 8 3 97592656 22 6 66456445 4 9 277935856 2 13 629083753 35 33 86588466 7 25 86588466 8 6 66456445 22 11 97592656 8 23 277935856 7 24
output:
274256402
result:
ok single line: '274256402'