QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409385 | #8638. 排序 | zzy0922 | 100 ✓ | 1000ms | 3884kb | C++14 | 1.9kb | 2024-05-12 00:37:41 | 2024-05-12 00:37:42 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int mod = 998244353;
inline int fmod(int x) {
return x >= mod ? x - mod : x;
}
inline void add(int &x, int v) {
x = fmod(x + v);
}
inline int fpow(int x, int k = mod - 2) {
int res = 1;
for (; k; k >>= 1, x = 1ll * x * x % mod)
if (k & 1)
res = 1ll * res * x % mod;
return res;
}
int n, m;
int f[105][105];
int C[105][105], S[105][105], c[105][105], fac[105], inv[105];
int main() {
for (int i = 0; i <= 100; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = fmod(C[i - 1][j - 1] + C[i - 1][j]);
}
S[0][0] = 1;
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= i; j++)
S[i][j] = fmod(1ll * j * S[i - 1][j] % mod + S[i - 1][j - 1]);
}
fac[0] = 1;
for (int i = 1; i <= 100; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
for (int i = 0; i <= 100; i++)
for (int j = 0; j <= i; j++)
c[i][j] = 1ll * S[i][j] * fac[j] % mod;
for (int i = 1; i <= 100; i++)
inv[i] = fpow(i);
std::cin >> n >> m;
for (int l = 1; l <= n; l++)
for (int l1 = 0; l1 + 1 <= l; l1++)
for (int l2 = 0; l2 + l1 + 1 <= l; l2++) {
int k = l - l1 - l2;
for (int p1 = (l1 != 0); p1 <= l1; p1++)
for (int p2 = (l2 != 0); p2 <= l2; p2++)
add(f[l1 + l2 + k][p1 + p2 + 1], 1ll * fmod(fmod(1ll * c[l2][p2] * f[l1][p1] % mod + 1ll * c[l1][p1] * f[l2][p2] % mod) + 1ll * c[l1][p1] * c[l2][p2] % mod * l % mod) * k % mod * inv[l1 + l2 + k] % mod * C[l1 + l2 + k][l1] % mod * C[l2 + k][l2] % mod);
}
int ans = 0;
for (int i = 1, c = 1; i <= n; i++) {
c = 1ll * (m - i + 1) * fpow(i) % mod * c % mod;
add(ans, 1ll * c * f[n][i] % mod);
}
std::cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 1ms
memory: 3768kb
input:
2 5
output:
70
result:
ok 1 number(s): "70"
Test #2:
score: 5
Accepted
time: 0ms
memory: 3704kb
input:
3 5
output:
615
result:
ok 1 number(s): "615"
Test #3:
score: 5
Accepted
time: 0ms
memory: 3712kb
input:
4 5
output:
4500
result:
ok 1 number(s): "4500"
Test #4:
score: 5
Accepted
time: 0ms
memory: 3836kb
input:
5 5
output:
29893
result:
ok 1 number(s): "29893"
Test #5:
score: 5
Accepted
time: 1ms
memory: 3772kb
input:
24 21
output:
122523734
result:
ok 1 number(s): "122523734"
Test #6:
score: 5
Accepted
time: 1ms
memory: 3832kb
input:
22 30
output:
942751666
result:
ok 1 number(s): "942751666"
Test #7:
score: 5
Accepted
time: 2ms
memory: 3660kb
input:
27 24
output:
156945891
result:
ok 1 number(s): "156945891"
Test #8:
score: 5
Accepted
time: 1ms
memory: 3784kb
input:
25 27
output:
236177959
result:
ok 1 number(s): "236177959"
Test #9:
score: 5
Accepted
time: 2ms
memory: 3716kb
input:
27 20
output:
458049658
result:
ok 1 number(s): "458049658"
Test #10:
score: 5
Accepted
time: 1ms
memory: 3712kb
input:
22 29
output:
139126090
result:
ok 1 number(s): "139126090"
Test #11:
score: 5
Accepted
time: 0ms
memory: 3768kb
input:
5 636664354
output:
889308944
result:
ok 1 number(s): "889308944"
Test #12:
score: 5
Accepted
time: 0ms
memory: 3764kb
input:
5 936013507
output:
971669244
result:
ok 1 number(s): "971669244"
Test #13:
score: 5
Accepted
time: 0ms
memory: 3820kb
input:
5 543315658
output:
762595320
result:
ok 1 number(s): "762595320"
Test #14:
score: 5
Accepted
time: 0ms
memory: 3708kb
input:
5 675078452
output:
561837734
result:
ok 1 number(s): "561837734"
Test #15:
score: 5
Accepted
time: 1000ms
memory: 3804kb
input:
100 630164947
output:
50609420
result:
ok 1 number(s): "50609420"
Test #16:
score: 5
Accepted
time: 774ms
memory: 3868kb
input:
95 595666255
output:
842083566
result:
ok 1 number(s): "842083566"
Test #17:
score: 5
Accepted
time: 624ms
memory: 3800kb
input:
91 694453675
output:
159909630
result:
ok 1 number(s): "159909630"
Test #18:
score: 5
Accepted
time: 949ms
memory: 3884kb
input:
99 959281108
output:
704080135
result:
ok 1 number(s): "704080135"
Test #19:
score: 5
Accepted
time: 998ms
memory: 3876kb
input:
100 672829497
output:
725853398
result:
ok 1 number(s): "725853398"
Test #20:
score: 5
Accepted
time: 590ms
memory: 3812kb
input:
90 832634235
output:
990411585
result:
ok 1 number(s): "990411585"