cf1173 D. Nauuo and Circle

2024-10-20 16:51:32

链接

[cf]http://codeforces.com/contest/1175/problem/F)

思路

当1在1的位置做dp[i]为i的子树所有的方案。

一条性质是i的子树所占圆上的位置一定一段连续的。

那\(f[i]\)的方案就是$(son[i]+(i!=1))!\prod\limits_{x \in i }f[x] \(
其实就是\)n*\prod\limits_{i=1}^{n}ru[i]! $

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+7,mod=998244353;

int n,ru[N],jc[N],ans=1;

int main() {

	scanf("%d",&n);

	for(int i=1,x,y;i<n;++i) {

		scanf("%d%d",&x,&y);

		ru[x]++,ru[y]++;

	}

	jc[1]=1;

	for(int i=2;i<=n;++i) jc[i]=1LL*jc[i-1]*i%mod;

	for(int i=1;i<=n;++i) ans=1LL*ans*(jc[ru[i]])%mod;

	cout<<1LL*n*ans%mod<<"\n";

	return 0;

}

最新文章

热门文章