QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558069#6623. Perfect MatchingsRillloRE 0ms3632kbC++236.7kb2024-09-11 13:58:012024-09-11 13:58:02

Judging History

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

  • [2024-09-11 13:58:02]
  • 评测
  • 测评结果：RE
  • 用时：0ms
  • 内存：3632kb
查看
  • [2024-09-11 13:58:01]
  • 提交

answer

#include<bits/stdc++.h>

using i64 = long long;
template<class T>
constexpr T power(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 MLong {
	i64 x;
	constexpr MLong() : x{} {}
	constexpr MLong(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;
	}
	explicit constexpr operator i64() const {
		return x;
	}
	constexpr MLong operator-() const {
		MLong res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MLong inv() const {
		assert(x != 0);
		return power(*this, getMod() - 2);
	}
	constexpr MLong &operator*=(MLong rhs) & {
		x = mul(x, rhs.x, getMod());
		return *this;
	}
	constexpr MLong &operator+=(MLong rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MLong &operator-=(MLong rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MLong &operator/=(MLong rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MLong operator*(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MLong operator+(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MLong operator-(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MLong operator/(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
		i64 v;
		is >> v;
		a = MLong(v);
		return is;
	}
	friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MLong lhs, MLong rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MLong lhs, MLong rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
	int x;
	constexpr MInt() : x{} {}
	constexpr MInt(i64 x) : x{norm(x % getMod())} {}
	
	static int Mod;
	constexpr static int getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(int Mod_) {
		Mod = Mod_;
	}
	constexpr int norm(int x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr int val() const {
		return x;
	}
	explicit constexpr operator int() const {
		return x;
	}
	constexpr MInt operator-() const {
		MInt res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MInt inv() const {
		assert(x != 0);
		return power(*this, getMod() - 2);
	}
	constexpr MInt &operator*=(MInt rhs) & {
		x = 1LL * 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();
	}
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

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) {
		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;
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout << std::fixed << std::setprecision(10);
	int n;
	std::cin >> n;
	std::vector<std::vector<int>> adj(2 * n);
	for (int i = 0; i < 2 * n - 1; i++) {
		int x, y;
		std::cin >> x >> y;
		x--, y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	auto dfs = [&](auto self, int x, int fa) -> std::vector<std::array<Z, 2>> {
		std::vector<std::array<Z, 2>> dp;
		dp.push_back({1, 0});
		
		for (auto y : adj[x]) {
			if (y == fa) continue;
			auto dp2 = self(self, y, x);
			int len1 = dp.size(), len2 = dp2.size();
			std::vector<std::array<Z, 2>> tmp(len1 + len2 + 1);
			for (int i = 0; i < dp.size(); i++) {
				for (int j = 0; j < dp2.size(); j++) {
					tmp[i + j][0] += (dp[i][0] * (dp2[j][0] + dp2[j][1])); 
					tmp[i + j][1] += dp[i][1] * (dp2[j][0] + dp2[j][1]);

					assert(i + j + 1 < tmp.size());	
					tmp[i + j + 1][1] += dp[i][0] * dp2[j][0];
				}
			}
			dp.resize(tmp.size());
			for (int i = 0; i < tmp.size(); i++) {
				dp[i] = tmp[i];
			}
		}

		return dp;
	};
	
	auto dp = dfs(dfs, 0, -1);
	Z ans = 0;
	int x = 1;
	for (int i = 0; i <= n; i++) {
		Z tmp = comb.binom(2 * (n - i), n - i) * comb.fac(n - i) / 
			power(2, n - i) * (dp[i][0] + dp[i][1]);
		
		ans += tmp * x;
		x *= -1;
	}
	// std::cout << comb.binom(2 * n, n) * comb.fac(n) / power(2, n) << "\n";
	std::cout << ans << "\n";
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

2
1 2
1 3
3 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

3
1 2
2 3
3 4
4 5
5 6

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10
2 1
3 2
4 2
5 3
6 3
7 5
8 4
9 3
10 5
11 3
12 9
13 11
14 8
15 5
16 1
17 4
18 1
19 11
20 19

output:

223263378

result:

ok 1 number(s): "223263378"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

10
2 1
3 1
4 1
5 1
6 5
7 3
8 7
9 3
10 2
11 3
12 5
13 12
14 10
15 11
16 10
17 4
18 14
19 4
20 4

output:

225215244

result:

ok 1 number(s): "225215244"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

10
2 1
3 1
4 3
5 3
6 5
7 3
8 5
9 3
10 8
11 2
12 1
13 11
14 2
15 3
16 3
17 2
18 11
19 10
20 3

output:

210104685

result:

ok 1 number(s): "210104685"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

10
2 1
3 2
4 3
5 1
6 2
7 5
8 2
9 3
10 2
11 10
12 7
13 12
14 2
15 2
16 15
17 2
18 6
19 15
20 8

output:

211263144

result:

ok 1 number(s): "211263144"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10
2 1
3 2
4 3
5 2
6 2
7 1
8 7
9 3
10 8
11 5
12 6
13 11
14 8
15 1
16 13
17 2
18 14
19 11
20 12

output:

226024809

result:

ok 1 number(s): "226024809"

Test #8:

score: -100
Runtime Error

input:

1977
2 1
3 1
4 1
5 4
6 4
7 1
8 3
9 5
10 2
11 3
12 2
13 3
14 2
15 9
16 9
17 2
18 17
19 5
20 16
21 2
22 2
23 15
24 16
25 22
26 14
27 6
28 4
29 24
30 25
31 28
32 15
33 27
34 32
35 24
36 10
37 18
38 15
39 33
40 3
41 27
42 3
43 35
44 15
45 11
46 19
47 21
48 4
49 28
50 6
51 3
52 14
53 14
54 14
55 25
56 18...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 22:38:57 | OpenSource Project