【题解】Luogu CF1172B Nauuo and Circle

原题传送门

题意：在圆上有n个节点（珂以构成凸多边形），让你给节点编号，使得将题目给你的边（一棵树）没有交叉

我们钦定1为这个树的根节点。任意节点\(x\)的一颗子树的点应该是圆弧上连续的一段（我也不知道我当时怎么就从HNOI2019d1t3多边形yy到这道题了），所以就是要将一段序列划分成\(siz[x]+1\)段，这个节点的贡献就是\(A_{siz[x]+1}^{siz[x]+1}\)。因为父子之间排序方案数互不干扰，所以最后答案就是所有节点贡献的乘积（根节点要特判，因为在一个环上，不能直接排列数）

考场上写的代码比较丑

#include <bits/stdc++.h>

#define N 200005

#define mod 998244353

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

struct edge{

	int to,next;

}e[N<<1];

int head[N],cnt;

inline void add(register int u,register int v)

{

	e[++cnt]=(edge){v,head[u]};

	head[u]=cnt;

}

int n,siz[N],sizs[N],fa[N],f[N],fac[N];

inline void dfs1(register int x)

{

	siz[x]=1;

	if(x!=1)

		sizs[x]=1;

	for(register int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa[x])

			continue;

		fa[v]=x;

		dfs1(v);

		siz[x]+=siz[v];

		++sizs[x];

	}

}

inline void dfs2(register int x)

{

	f[x]=fac[sizs[x]];

	for(register int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa[x])

			continue;

		dfs2(v);

		f[x]=1ll*f[x]*f[v]%mod;

	}

}

int main()

{

	fac[0]=1;

	for(register int i=1;i<N;++i)

		fac[i]=1ll*i*fac[i-1]%mod;

	n=read();

	for(register int i=1;i<n;++i)

	{

		int u=read(),v=read();

		add(u,v),add(v,u);

	}

	dfs1(1);

	dfs2(1);

	write(1ll*f[1]*n%mod);

	return 0;

}

巴特西

【题解】Luogu CF1172B Nauuo and Circle

原题传送门

题意：在圆上有n个节点（珂以构成凸多边形），让你给节点编号，使得将题目给你的边（一棵树）没有交叉

考场上写的代码比较丑

最新文章

热门文章