QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245765 | #6623. Perfect Matchings | 0x4F5DA2 | RE | 0ms | 0kb | C++14 | 2.6kb | 2023-11-10 11:42:11 | 2023-11-10 11:42:11 |
answer
#include <cstdio>
#define int long long
const int maxn = 2000;
const int mp = 998244353;
int n;
struct node{
int nxt;
int to;
}edge[maxn * 4 + 10];
int head[maxn * 2 + 10];
int top;
void AddEdge(int u, int v){
++top;
edge[top].nxt = head[u];
edge[top].to = v;
head[u] = top;
return ;
}
long long ans = 0;
long long f[maxn * 2 + 10][maxn + 10][2];
//int temp[maxn + 10];
int siz[maxn * 2 + 10];
void dfs(int x, int fa){
siz[x] = 1;
f[x][0][0] = 1;
f[x][0][1] = 0;
for(int i = head[x]; i; i = edge[i].nxt){
int y = edge[i].to;
if(y != fa){
dfs(y, x);
siz[x] = siz[x] + siz[y];
for(int j = siz[x]; j > 0; --j){
//k = 0
f[x][j][0] = f[x][j][0] * (f[y][0][0] + f[y][0][1]) % mp;
f[x][j][1] = f[x][j][1] * (f[y][0][0] + f[y][0][1]) % mp;
if(1 <= j){
f[x][j][1] = (f[x][j][1] + f[x][j - 1][0] * f[y][0][0] % mp) % mp;
}
//
for(int k = 1; k <= siz[y] / 2; ++k){
if(k <= j){
f[x][j][0] = (f[x][j][0] + f[x][j - k][0] * (f[y][k][0] + f[y][k][1]) % mp) % mp;
f[x][j][1] = (f[x][j][1] + f[x][j - k][1] * (f[y][k][0] + f[y][k][1]) % mp) % mp;
}
if(k + 1 <= j){
f[x][j][1] = (f[x][j][1] + f[x][j - k - 1][0] * f[y][k][0] % mp) % mp;
}
}
}
}
}
return ;
}
long long ny[maxn * 2 + 10];
long long jc[maxn * 2 + 10];
long long jcny[maxn * 2 + 10];
long long pow_2[maxn * 2 + 10];
long long pow_2ny[maxn * 2 + 10];
long long fun(int cnt){
return (jc[cnt] * pow_2ny[cnt / 2] % mp) * jcny[cnt/2] % mp;
}
signed main(){
scanf("%d", &n);
pow_2[0] = 1;
pow_2[1] = 2;
pow_2ny[0] = 1;
pow_2ny[1] = 499122177;
jc[0] = 1;
jc[1] = 1;
jcny[0] = 1;
jcny[1] = 1;
ny[0] = 0;
ny[1] = 1;
for(int i = 2; i <= 2 * n; ++i){
//inv[i] = (long long)(p - p / i) * inv[p % i] % p;
ny[i] = (mp - mp / i) * ny[mp % i] % mp;
pow_2[i] = pow_2[i - 1] * 2 % mp;
pow_2ny[i] = pow_2ny[i - 1] * ny[2] % mp;
jc[i] = jc[i - 1] * i % mp;
jcny[i] = jcny[i - 1] * ny[i] % mp;
}
//
/*for(int i = 1; i <= 2 * n; ++i){
if(pow_2[i] >
}*/
//pow_2ny[2] = ny[2];
int u, v;
for(int i = 1; i < 2 * n; ++i){
scanf("%d%d", &u, &v);
AddEdge(u, v);
AddEdge(v, u);
}
dfs(1, 0);
/*for(int i = 0; i <= siz[1] / 2; ++i){
printf("%lld %lld\n", f[1][i][0], f[1][i][1]);
}*/
for(int i = 0; i <= n; ++i){
if(i & 1)
ans = (ans - (f[1][i][1] + f[1][i][0]) * fun(2 * n - 2 * i) % mp + mp) % mp;
else
ans = (ans + (f[1][i][1] + f[1][i][0]) * fun(2 * n - 2 * i) % mp) % mp;
}
printf("%lld", ans);
return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
2 1 2 1 3 3 4