QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722618#9611. 木桶效应JWRuixi100 ✓617ms13600kbC++173.9kb2024-11-07 19:40:142024-11-07 19:40:22

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 19:40:22]
  • 评测
  • 测评结果:100
  • 用时:617ms
  • 内存:13600kb
  • [2024-11-07 19:40:14]
  • 提交

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();
  }
}
// I love WHQ!

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 5584kb

input:

5 3 0

output:

21412920

result:

ok single line: '21412920'

Test #2:

score: 4
Accepted
time: 1ms
memory: 5748kb

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: 5736kb

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: 5660kb

input:

7 3 0

output:

160221085

result:

ok single line: '160221085'

Test #5:

score: 8
Accepted
time: 1ms
memory: 7748kb

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: 5840kb

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: 5864kb

input:

50 1 0

output:

263941435

result:

ok single line: '263941435'

Test #8:

score: 8
Accepted
time: 1ms
memory: 5632kb

input:

43 2 0

output:

136378346

result:

ok single line: '136378346'

Test #9:

score: 8
Accepted
time: 1ms
memory: 5616kb

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: 5608kb

input:

50 292247015 0

output:

226872193

result:

ok single line: '226872193'

Test #11:

score: 12
Accepted
time: 1ms
memory: 5696kb

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: 8532kb

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: 2ms
memory: 8696kb

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: 2ms
memory: 8748kb

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: 0ms
memory: 8412kb

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: 8736kb

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: 11804kb

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: 13052kb

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: 11012kb

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: 2ms
memory: 12740kb

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: 9ms
memory: 12856kb

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: 54ms
memory: 11892kb

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: 15ms
memory: 12808kb

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: 61ms
memory: 12780kb

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: 0ms
memory: 12724kb

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: 12ms
memory: 11328kb

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: 21ms
memory: 12748kb

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: 213ms
memory: 12148kb

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: 48ms
memory: 12132kb

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: 12852kb

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: 11992kb

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: 19ms
memory: 11644kb

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: 36ms
memory: 11500kb

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: 264ms
memory: 13600kb

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: 89ms
memory: 12676kb

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: 12328kb

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: 25ms
memory: 11688kb

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: 83ms
memory: 13072kb

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: 134ms
memory: 12352kb

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: 12ms
memory: 11872kb

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'