题解：CF1172B Nauuo and Circle

首先，观察样例，发现真正不同的只有 4 个，也就是圆心正上方的数是 1 的情况，剩下的都是旋转得到的。所以以

1

为根讨论，最后输出

ans \times n

。

手玩一下，发现连边就会将各个子树隔绝，所以一个子树的排布是要连续的。而且所有的子树，最终是不会留下空位的。

我们定义

f_u

为以 u 为根的子树的方案数，有

d_u

个子树。那么它们可以随意排列，贡献就是

(d_u +1)!

，每个子树的方案数也是独立的。所以有：

f_u = d_u! \times \prod\limits_{v \in son_u}f_v

我们已经把节点

1

固定了，没有考虑

u

节点，如果不是根的话，节点

u

也可以和它的子树一起排列，这种情况下，上面式子的

d_u

要变成

(d_u + 1)

。

CPP

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5+10, mod = 998244353;
int fac[N],n;
vector<int>e[N];

int f[N];
void dfs(int u,int fa) {
	f[u] = fac[e[u].size()];
	for(int v:e[u]) {
		if(v == fa) continue;
		dfs(v,u);
		f[u] = 1ll * f[u] * f[v] % mod; 
	}
}
int main() {
	cin>>n;
	fac[0] = 1;
	for(int i=1;i<=n;i++) fac[i] = 1LL * fac[i-1] * i % mod;
	for(int i=1,u,v;i<n;i++) cin>>u>>v, e[u].push_back(v), e[v].push_back(u);
	dfs(1,1);
	cout << 1ll * f[1] * n % mod;
	return 0;
}

题解：CF1172B Nauuo and Circle

文章操作

相关推荐

评论

题解：CF1172B Nauuo and Circle