QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751953#6623. Perfect Matchings777ML 679ms443352kbC++206.4kb2024-11-15 21:23:482024-11-15 21:23:49

Judging History

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

  • [2024-11-15 21:23:49]
  • 评测
  • 测评结果:ML
  • 用时:679ms
  • 内存:443352kb
  • [2024-11-15 21:23:48]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
//using i128 = __int128_t;
//#define int long long
typedef pair<int,int> PII;
typedef long long ll;
inline void read(int &x){
    char ch=getchar();int f=1;x=0;
    while(!isdigit(ch) && ch^'-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}
void write(int x){
    if(x<0)
    putchar('-'),x=-x;
    if(x>9)
    write(x/10);
    putchar(x%10+'0');
    return;
}

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 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 power(*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<i64>(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;
int n;
void rCL(){
	cin>>n;
	vector<vector<int>>e(2*n+1);
	for(int i=1;i<=2*n-1;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}    

	vector<vector<vector<Z>>>f(2*n+1,vector<vector<Z>>(n+3,vector<Z>(2,0)));
	vector<int>sz(2*n+1);

	auto dfs=[&](auto dfs,int u,int fa)->void{
       // cout<<u<<endl;
		sz[u]=1;f[u][0][0]=1;
		for(auto v:e[u]){
			vector<vector<Z>>g(n+3,vector<Z>(2,0));
            //g[0][0]=1;
			if(v==fa)continue;
			dfs(dfs,v,u);

			for(int i=0;i<=sz[u]/2;i++){
				for(int j=0;j<=sz[v]/2;j++){
					g[i+j][0]+=f[u][i][0]*(f[v][j][0]+f[v][j][1]);
					g[i+j][1]+=f[u][i][1]*(f[v][j][0]+f[v][j][1]);
					g[i+1+j][1]+=f[u][i][0]*f[v][j][0];
				}
			}
            //cout<<"U"<<u<<endl;
			for(int i=0;i<=sz[u]/2+sz[v]/2+1;i++){
               // cout<<u<<' '<<i<<' '<<f[u][i][0]<<endl;
                //cout<<u<<' '<<i<<' '<<f[u][i][1]<<endl;
				f[u][i][0]=g[i][0];
				f[u][i][1]=g[i][1];
			}

			sz[u]+=sz[v];
		}
	};
    Z res=0;
    vector<Z>f2(n+1);
    dfs(dfs,1,0);
    //cout<<1<<endl;
    f2[0]=1;
    for(int i=1;i<=n;i++){
        if(i==1)f2[i]=(Z)1/2;
        else{
            f2[i]=f2[i-1]/2;
        }
    }
    for(int i=0;i<=n;i++){
        Z x=f[1][i][0]+f[1][i][1];
       // cout<<f[1][i][0]<<' '<<f[1][i][1]<<endl;
       // Z y=1;
        Z y=comb.binom(2*n-2*i,n-i)*comb.fac(n-i)*f2[n-i];
        //cout<<comb.binom(2*n-2*i,n-i)<<' '<<comb.fac(n-i)<<' '<<f2[n-i]<<endl;
        //cout<<"y"<<y<<endl;
        if(i&1){
            res-=x*y;
        }else{
            res+=x*y;
        }
    }
    cout<<res<<endl;




}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int O_o=1;
    while(O_o--){
        rCL();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
1 2
1 3
3 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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: 3612kb

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: 3580kb

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: 3576kb

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: 3576kb

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: 0
Accepted
time: 658ms
memory: 433592kb

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:

337494603

result:

ok 1 number(s): "337494603"

Test #9:

score: 0
Accepted
time: 618ms
memory: 409764kb

input:

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

output:

850212664

result:

ok 1 number(s): "850212664"

Test #10:

score: 0
Accepted
time: 613ms
memory: 420336kb

input:

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

output:

148051811

result:

ok 1 number(s): "148051811"

Test #11:

score: 0
Accepted
time: 617ms
memory: 409660kb

input:

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

output:

280704181

result:

ok 1 number(s): "280704181"

Test #12:

score: 0
Accepted
time: 656ms
memory: 433256kb

input:

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

output:

627986542

result:

ok 1 number(s): "627986542"

Test #13:

score: 0
Accepted
time: 679ms
memory: 443352kb

input:

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

output:

927794050

result:

ok 1 number(s): "927794050"

Test #14:

score: 0
Accepted
time: 672ms
memory: 433280kb

input:

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

output:

685071441

result:

ok 1 number(s): "685071441"

Test #15:

score: 0
Accepted
time: 589ms
memory: 409792kb

input:

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

output:

632229124

result:

ok 1 number(s): "632229124"

Test #16:

score: 0
Accepted
time: 621ms
memory: 419328kb

input:

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

output:

175426091

result:

ok 1 number(s): "175426091"

Test #17:

score: 0
Accepted
time: 631ms
memory: 422272kb

input:

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

output:

620932394

result:

ok 1 number(s): "620932394"

Test #18:

score: 0
Accepted
time: 632ms
memory: 419188kb

input:

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

output:

990615942

result:

ok 1 number(s): "990615942"

Test #19:

score: 0
Accepted
time: 644ms
memory: 443236kb

input:

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

output:

814855336

result:

ok 1 number(s): "814855336"

Test #20:

score: 0
Accepted
time: 653ms
memory: 427308kb

input:

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

output:

935127715

result:

ok 1 number(s): "935127715"

Test #21:

score: 0
Accepted
time: 670ms
memory: 441424kb

input:

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

output:

610654989

result:

ok 1 number(s): "610654989"

Test #22:

score: 0
Accepted
time: 627ms
memory: 418620kb

input:

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

output:

329465487

result:

ok 1 number(s): "329465487"

Test #23:

score: -100
Memory Limit Exceeded

input:

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

output:

866759945

result: