QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #409348 | #8638. 排序 | zzy0922 | 100 ✓ | 499ms | 8092kb | C++14 | 2.6kb | 2024-05-11 22:19:51 | 2024-05-11 22:19:52 |
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 con[105][105][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; l1 + l2 + 1 <= l; l2++)
con[l][l1][l2] = (__int128_t(1) * (l - l1 - l2) * inv[l] * C[l][l1] * C[l - l1][l2]) % mod;
// std::cout << "OK:" << l << ' ' << l1 << ' ' << l2 << ' ' << con[l][l1][l2] << '\n';
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++) {
//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 sum = (__int128_t(1) * c[l2][p2] * f[l1][p1] + __int128_t(1) * c[l1][p1] * f[l2][p2] + __int128_t(1) * c[l1][p1] * c[l2][p2] * l) % mod;
// std::cout << l << ' ' << l1 << ' ' << l2 << ' ' << con[l][l1][l2] << '\n';
add(f[l1 + l2 + k][p1 + p2 + 1], 1ll * sum * con[l][l1][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';
}
詳細信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 3744kb
input:
2 5
output:
70
result:
ok 1 number(s): "70"
Test #2:
score: 5
Accepted
time: 1ms
memory: 3692kb
input:
3 5
output:
615
result:
ok 1 number(s): "615"
Test #3:
score: 5
Accepted
time: 1ms
memory: 3996kb
input:
4 5
output:
4500
result:
ok 1 number(s): "4500"
Test #4:
score: 5
Accepted
time: 1ms
memory: 3752kb
input:
5 5
output:
29893
result:
ok 1 number(s): "29893"
Test #5:
score: 5
Accepted
time: 0ms
memory: 4196kb
input:
24 21
output:
122523734
result:
ok 1 number(s): "122523734"
Test #6:
score: 5
Accepted
time: 1ms
memory: 3932kb
input:
22 30
output:
942751666
result:
ok 1 number(s): "942751666"
Test #7:
score: 5
Accepted
time: 1ms
memory: 4168kb
input:
27 24
output:
156945891
result:
ok 1 number(s): "156945891"
Test #8:
score: 5
Accepted
time: 2ms
memory: 8024kb
input:
25 27
output:
236177959
result:
ok 1 number(s): "236177959"
Test #9:
score: 5
Accepted
time: 0ms
memory: 3944kb
input:
27 20
output:
458049658
result:
ok 1 number(s): "458049658"
Test #10:
score: 5
Accepted
time: 1ms
memory: 3876kb
input:
22 29
output:
139126090
result:
ok 1 number(s): "139126090"
Test #11:
score: 5
Accepted
time: 1ms
memory: 3656kb
input:
5 636664354
output:
889308944
result:
ok 1 number(s): "889308944"
Test #12:
score: 5
Accepted
time: 1ms
memory: 3932kb
input:
5 936013507
output:
971669244
result:
ok 1 number(s): "971669244"
Test #13:
score: 5
Accepted
time: 1ms
memory: 5792kb
input:
5 543315658
output:
762595320
result:
ok 1 number(s): "762595320"
Test #14:
score: 5
Accepted
time: 0ms
memory: 3652kb
input:
5 675078452
output:
561837734
result:
ok 1 number(s): "561837734"
Test #15:
score: 5
Accepted
time: 499ms
memory: 8012kb
input:
100 630164947
output:
50609420
result:
ok 1 number(s): "50609420"
Test #16:
score: 5
Accepted
time: 378ms
memory: 7140kb
input:
95 595666255
output:
842083566
result:
ok 1 number(s): "842083566"
Test #17:
score: 5
Accepted
time: 300ms
memory: 6452kb
input:
91 694453675
output:
159909630
result:
ok 1 number(s): "159909630"
Test #18:
score: 5
Accepted
time: 463ms
memory: 8092kb
input:
99 959281108
output:
704080135
result:
ok 1 number(s): "704080135"
Test #19:
score: 5
Accepted
time: 485ms
memory: 6796kb
input:
100 672829497
output:
725853398
result:
ok 1 number(s): "725853398"
Test #20:
score: 5
Accepted
time: 284ms
memory: 7868kb
input:
90 832634235
output:
990411585
result:
ok 1 number(s): "990411585"