kmjp's blog

競技プログラミング参加記です

Codeforces #564 Div1 B. Nauuo and Circle

なんかだんだんCFの記事書くの遅れてきてるけど、しばらくコンテスト頻度まばらになりそうだし徐々に追いかけるか…。
https://codeforces.com/contest/1172/problem/B

問題

N頂点の木を成す無向グラフが与えられる。
さて、円周上にN個の点がある。
元のグラフの点を、これらのN個の点に1対1で対応付け、各辺に対応する頂点同士を線分でつなぐとする。
頂点の対応付けはN!通り考えられるが、辺が交差しないのは何通りか。

解法

1番の頂点からDFSで、各頂点における親頂点以外の点の相対的な順番の組み合わせを掛けよう。
もし頂点vが子頂点をp個持ってたとする。
このp個の相対的な順番はp!通りであり、またこれらp個のうちいくつがvの右側にあるかを考えると(p+1)通りとなる。
よって(p+1)!を掛ければよい。

これを各頂点で行ったうえで、1番の頂点の配置N通りを掛ければよい。

以下のコードでは律儀にDFSやったけど、(辺数+1)!を愚直に掛けるだけでよかったかもね。

int N;
vector<int> E[202020];
ll mo=998244353;
ll fact[202020];

ll dfs(int cur,int pre) {
	ll ret=1;
	int num=0;
	FORR(e,E[cur]) if(e!=pre) {
		num++;
		ret=ret*dfs(e,cur)%mo;
	}
	
	if(cur!=0) ret=ret*fact[num]%mo*(num+1)%mo;
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	fact[0]=1;
	for(i=1;i<=200020;i++) fact[i]=fact[i-1]*i%mo;
	
	cout<<(N*dfs(0,0)%mo*fact[E[0].size()]%mo)<<endl;
	
	
}

まとめ

3か月近く前の問題、記憶から薄れてくるけどあえて遅れてブログを書くことで復習になるので悪い点ばかりでもない。