QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409382#8638. 排序Nelofus85 825ms4044kbC++204.6kb2024-05-12 00:13:552024-05-12 00:13:56

Judging History

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

  • [2024-05-12 00:13:56]
  • 评测
  • 测评结果:85
  • 用时:825ms
  • 内存:4044kb
  • [2024-05-12 00:13:55]
  • 提交

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"