QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#709829 | #6623. Perfect Matchings | hansue | WA | 7ms | 66596kb | C++20 | 2.4kb | 2024-11-04 17:02:11 | 2024-11-04 17:02:15 |
Judging History
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