QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#767313#6623. Perfect MatchingsHHAZTL 11ms68696kbC++234.8kb2024-11-20 20:31:422024-11-20 20:31:46

Judging History

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

  • [2024-11-20 20:31:46]
  • 评测
  • 测评结果：TL
  • 用时：11ms
  • 内存：68696kb
查看
  • [2024-11-20 20:31:42]
  • 提交

answer

#pragma GCC optimze(2)
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define sz(t) (int)t.size()
#define all(t) t.begin(), t.end()
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl;
typedef long long ll;
using namespace std;
typedef pair<ll, ll> pll;
const ll N = 4002;
const ll mod = 998244535;

int n;
vector<int>ve[N];
int c[N][N], siz[N], f[N];
ll dp[N][2][N];
ll temp[2][4002];

struct Qmod
{
    ll m, p;
    void init(ll pp) {m = ((__int128)1 << 64) / pp; p = pp;}
    ll operator ()(ll x)
    {
        return x - ((__int128)(x) * m >> 64) * p;
    }
}mo;

void init_com()
{
    rep(i, 0, N - 1) c[i][0] = 1;
    rep(i, 1, N - 1)
    {
        rep(j, 1, i)
        {
            c[i][j] = mo(c[i - 1][j] + c[i - 1][j - 1]);
        }
    }
    f[0] = 1;
    rep(i, 1, N - 1)
    {
        f[i] = mo(f[i - 1] * i);
    }
}

void dfs(ll u, ll fa)
{
    siz[u]++;
    dp[u][1][0] = 1;
    for(auto v : ve[u])
    {
        if(v != fa)
        {
            dfs(v, u);
            rep(i, 0, 1)
            {
                rep(j, 0, siz[u] + siz[v])
                {
                    temp[i][j] = 0;
                }
            }
            rep(i, 0, siz[u] - 1)
            {
                rep(j, 0, siz[v] - 1)
                {
                    rep(k, max(0ll, llabs(i - j) - 2), min(i + j + 2, n - siz[u] - siz[v]))
                    {
                        int x;
                        x = i + j - k;
                        if(x % 2 == 0 && x >= 0)
                        {
                            x /= 2;
                            temp[0][k] += mo(mo(mo(mo(dp[u][0][i] * dp[v][0][j]) * c[i][x]) * c[j][x]) * f[x]);
                            temp[0][k] = mo(temp[0][k]);
                        }
                        x = i + j - k + 1;
                        if(x % 2 == 0 && x >= 0)
                        {
                            x /= 2;
                            temp[0][k] += mo(mo(mo(mo(dp[u][0][i] * dp[v][1][j]) * c[i][x]) * c[j + 1][x]) * f[x]);
                            temp[0][k] = mo(temp[0][k]);
                        }
                        x = i + j - k + 1;
                        if(x % 2 == 0 && x / 2 >= 1)
                        {
                            x /= 2;
                            temp[0][k] += mo(mo(mo(mo(dp[u][1][i] * dp[v][0][j]) * c[i][x - 1]) * c[j][x]) * f[x]);
                            temp[0][k] = mo(temp[0][k]);
                        }
                        x = i + j - k + 2;
                        if(x % 2 == 0 && x / 2 >= 1)
                        {
                            x /= 2;
                            temp[0][k] += mo(mo(mo(mo(dp[u][1][i] * dp[v][1][j]) * c[i][x - 1]) * c[j][x]) * f[x]);
                            temp[0][k] = mo(temp[0][k]);
                            temp[0][k] += mo(mo(mo(mo(mo(dp[u][1][i] * dp[v][1][j]) * c[i][x - 1]) * c[j][x - 1]) * f[x - 1]) * (x - 1));
                            temp[0][k] = mo(temp[0][k]);
                        }
                        x = i + j - k;
                        if(x % 2 == 0 && x >= 0)
                        {
                            x /= 2;
                            temp[1][k] += mo(mo(mo(mo(dp[u][1][i] * dp[v][0][j]) * c[i][x]) * c[j][x]) * f[x]);
                            temp[1][k] = mo(temp[1][k]);
                        }
                        x = i + j + 1 - k;
                        if(x % 2 == 0 && x >= 0)
                        {
                            x /= 2;
                            temp[1][k] += mo(mo(mo(mo(dp[u][1][i] * dp[v][1][j]) * c[i][x]) * c[j][x]) * f[x]);
                            temp[1][k] = mo(temp[1][k]);
                            if(x) temp[1][k] += mo(mo(mo(mo(dp[u][1][i] * dp[v][1][j]) * c[i][x]) * c[j][x - 1]) * f[x]);
                            temp[1][k] = mo(temp[1][k]);
                        }
                    }
                }
            }
            siz[u] += siz[v];
            rep(i, 0, 1)
            {
                rep(j, 0, siz[u])
                {
                    dp[u][i][j] = temp[i][j];
                }
            }
        }
    }
}

void solve()
{
    cin >> n;
    n *= 2;
    rep(i, 2, n)
    {
        ll u, v;
        cin >> u >> v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    dfs(1, 0);
    cout << dp[1][0][0];
}
//562347296
int main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);

    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1;
    init_com();
    mo.init(mod);
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 66864kb

input:

2
1 2
1 3
3 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 7ms
memory: 68664kb

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: 6ms
memory: 68696kb

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: 11ms
memory: 66824kb

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: 7ms
memory: 68460kb

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: 8ms
memory: 66980kb

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: 8ms
memory: 68456kb

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
Time Limit Exceeded

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 繁體中文 简体中文

服务器时间: 2024-12-02 22:48:15 | 开源项目