QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#709829#6623. Perfect MatchingshansueWA 7ms66596kbC++202.4kb2024-11-04 17:02:112024-11-04 17:02:15

Judging History

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

  • [2024-11-04 17:02:15]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:66596kb
  • [2024-11-04 17:02:11]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
const int N = 2000;
const LL mod = 998244353;

    int n;
    vector<int>g[N + 3];
    int sz[N + 3];
    LL f[N + 3][N + 3][2];

void dfs(int u, int fr){
    sz[u] = 0;
    for(int i = 0, v; i < g[u].size(); i++){
        v = g[u][i];
        if(v == fr)
            continue;

        // if(u == 1 && v == 2)
        //     printf("1->2\n");
        // if(u == 1 && v == 3)
        //     printf("1->3\n");

        dfs(v, u);
        sz[u] += sz[v];
    }
    sz[u]++;

    f[u][0][0] = 1;

    for(int vi = 0, v; vi < g[u].size(); vi++){
        v = g[u][vi];
        if(v == fr)
            continue;
        
        for(int i = sz[u] / 2; i >= 1; i--)
            for(int j = sz[v] / 2; j >= 0; j--){
                if(j > 0 && i - j >= 0){
                    (f[u][i][0] += f[u][i - j][0] * (f[v][j][0] + f[v][j][1]) % mod) %= mod;
                    (f[u][i][1] += f[u][i - j][1] * (f[v][j][0] + f[v][j][1]) % mod) %= mod;
                }
                if(i - j >= 1)
                    (f[u][i][1] += f[u][i - j - 1][0] * f[v][j][0] % mod) %= mod;
            }
    }
}

    LL d[N + 3];

int main(){
    scanf("%d", &n);
    for(int i = 1, u, v; i <= 2 * n - 1; i++){
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(f, 0 ,sizeof f);
    dfs(1, 0);

    // printf("\n");
    // printf("[ ][ ]");
    // for(int i = 0; i <= 2 * n - 1; i++)
    //     printf("%4d", i);
    // printf("\n");
    // for(int u = 1; u <= 2 * n; u++){
    //     printf("[%d][0]", u);
    //     for(int i = 0; i <= 2 * n - 1; i++)
    //         printf("%4lld", f[u][i][0]);
    //     printf("\n");
    //     printf("[%d][1]", u);
    //     for(int i = 0; i <= 2 * n - 1; i++)
    //         printf("%4lld", f[u][i][1]);
    //     printf("\n");
    // }
    // printf("\n");

    d[0] = d[1] = 1;
    for(int i = 2; i <= n; i++)
        (d[i] = d[i - 1] * (2 * i - 1) % mod) %= mod;
    
    for(int i = 1; i <= n; i++)
        printf("%lld\n", d[i]);
    printf("\n");

    LL ans = 0;
    for(int i = 0; i <= n; i++)
        (ans += ((i & 1)?(-1):(1)) * ((f[1][i][0] + f[1][i][1]) * d[n - i] % mod) + mod) %= mod;
    
    printf("%lld", ans);

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 66596kb

input:

2
1 2
1 3
3 4

output:

1
3

1

result:

wrong answer Output contains longer sequence [length = 3], but answer contains 1 elements