QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409382 | #8638. 排序 | Nelofus | 85 | 825ms | 4044kb | C++20 | 4.6kb | 2024-05-12 00:13:55 | 2024-05-12 00:13:56 |
Judging History
answer
// Code by Heratino & Nelofus
// Narcissus & どうか安寧な記憶を
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
constexpr T fpow(T a, i64 b) {
T res {1};
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MInt {
i64 x;
constexpr MInt() : x {0} {}
constexpr MInt(i64 x) : x {norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
return fpow(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
if (getMod() < (1ULL << 31)) {
x = x * rhs.x % int(getMod());
} else {
x = mul(x, rhs.x, getMod());
}
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(MInt lhs, MInt rhs) {
return lhs.val() < rhs.val();
}
};
template<>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;
struct Comb {
int n;
std::vector<Z> _fac;
std::vector<Z> _invfac;
std::vector<Z> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
m = std::min(0ll + m, Z::getMod() - 1);
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
} comb;
constexpr int N = 110;
int n, m;
// 斯特林数
Z S[N][N];
Z f[N][N];
Z g[N][N];
int main() {
std::cin >> n >> m;
S[0][0] = 1;
g[0][0] = 1;
for (int i = 1; i < N; i++)
for (int j = 1; j <= i; j++) {
S[i][j] = j * S[i - 1][j] + S[i - 1][j - 1];
g[i][j] = S[i][j] * comb.fac(j);
}
auto multiBinom = [&](int x, int y, int z) -> Z {
return comb.fac(x + y + z) * comb.invfac(x) * comb.invfac(y) * comb.invfac(z);
};
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
for (int k = 1; k <= y; k++) {
for (int c = 1; c <= x; c++) {
Z fac = c * comb.inv(x);
Z res = 0;
for (int l1 = 0 + (k - 1); l1 <= x - c; l1++) {
if (l1 && !(k - 1))
break;
int l2 = x - c - l1;
if (l2 < y - k)
break;
if (l2 && !(y - k))
continue;
Z part1 = multiBinom(l1, c, l2);
Z part2 = g[l1][k - 1] * f[l2][y - k] + g[l2][y - k] * f[l1][k - 1] + g[l1][k - 1] * g[l2][y - k] * x;
res += part1 * part2;
}
f[x][y] += fac * res;
}
}
}
}
Z ans = 0;
Z C = 1;
for (int i = 1; i <= n; i++) {
C *= (m - i + 1) * comb.inv(i);
ans += C * f[n][i];
}
std::cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 1ms
memory: 4032kb
input:
2 5
output:
70
result:
ok 1 number(s): "70"
Test #2:
score: 5
Accepted
time: 1ms
memory: 3808kb
input:
3 5
output:
615
result:
ok 1 number(s): "615"
Test #3:
score: 5
Accepted
time: 0ms
memory: 4044kb
input:
4 5
output:
4500
result:
ok 1 number(s): "4500"
Test #4:
score: 5
Accepted
time: 0ms
memory: 3800kb
input:
5 5
output:
29893
result:
ok 1 number(s): "29893"
Test #5:
score: 5
Accepted
time: 2ms
memory: 3828kb
input:
24 21
output:
122523734
result:
ok 1 number(s): "122523734"
Test #6:
score: 5
Accepted
time: 1ms
memory: 3768kb
input:
22 30
output:
942751666
result:
ok 1 number(s): "942751666"
Test #7:
score: 5
Accepted
time: 0ms
memory: 3772kb
input:
27 24
output:
156945891
result:
ok 1 number(s): "156945891"
Test #8:
score: 5
Accepted
time: 2ms
memory: 3988kb
input:
25 27
output:
236177959
result:
ok 1 number(s): "236177959"
Test #9:
score: 5
Accepted
time: 3ms
memory: 3996kb
input:
27 20
output:
458049658
result:
ok 1 number(s): "458049658"
Test #10:
score: 5
Accepted
time: 1ms
memory: 3832kb
input:
22 29
output:
139126090
result:
ok 1 number(s): "139126090"
Test #11:
score: 5
Accepted
time: 0ms
memory: 3808kb
input:
5 636664354
output:
889308944
result:
ok 1 number(s): "889308944"
Test #12:
score: 5
Accepted
time: 0ms
memory: 3744kb
input:
5 936013507
output:
971669244
result:
ok 1 number(s): "971669244"
Test #13:
score: 5
Accepted
time: 0ms
memory: 3744kb
input:
5 543315658
output:
762595320
result:
ok 1 number(s): "762595320"
Test #14:
score: 5
Accepted
time: 1ms
memory: 3808kb
input:
5 675078452
output:
561837734
result:
ok 1 number(s): "561837734"
Test #15:
score: 0
Time Limit Exceeded
input:
100 630164947
output:
50609420
result:
Test #16:
score: 5
Accepted
time: 825ms
memory: 3880kb
input:
95 595666255
output:
842083566
result:
ok 1 number(s): "842083566"
Test #17:
score: 5
Accepted
time: 667ms
memory: 3768kb
input:
91 694453675
output:
159909630
result:
ok 1 number(s): "159909630"
Test #18:
score: 0
Time Limit Exceeded
input:
99 959281108
output:
704080135
result:
Test #19:
score: 0
Time Limit Exceeded
input:
100 672829497
output:
725853398
result:
Test #20:
score: 5
Accepted
time: 631ms
memory: 3884kb
input:
90 832634235
output:
990411585
result:
ok 1 number(s): "990411585"