QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245765#6623. Perfect Matchings0x4F5DA2RE 0ms0kbC++142.6kb2023-11-10 11:42:112023-11-10 11:42:11

Judging History

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

  • [2023-11-10 11:42:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: