[BOJ 26079 // C++] 곰곰이의 벼락치기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26079번 문제인 곰곰이와 하카타이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26079 

26079번: 곰곰이의 벼락치기

먼저 봐야 하는 강의가 없는 강의는 "0번 강의"라는 가상의 강의를 먼저 봐야하는 것으로 취급하면, 각 1~N번 강의는 먼저봐야 하는 강의가 정확히 하나씩 정해져있으므로 이 관찰을 바탕으로 문제의 상황을 0을 루트로 갖는 트리로 모델링할 수 있다. 이 때, (루트를 제외한) 모든 각 노드에 대응되는 강의는 자신의 부모에 대응되는 강의를 먼저 본 뒤 볼 수 있다는 성질이 있음을 확인하자.

 

각 강의에 대하여, 강의 X를 루트로 갖는 서브트리에 대한 강의를 듣는 순서의 경우의 수는 각 자식을 루트로 갖는 서브트리에 대한 강의를 듣는 경우의 수들의 곱과, 각 자식의 서브트리에 속한 노드들을 서브트리별로 색을 구분해 칠했을 때 이 노드들을 색을 기준으로 나열하는 경우의 수를 곱하는 것으로 계산할 수 있다. 이를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll fact[200001];
ll invfact[200001];

void init() {
	fact[0] = fact[1] = 1;
	for (ll i = 2; i < 200001; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
	}
	invfact[0] = invfact[1] = 1;
	for (ll i = 2; i < 200001; i++) {
		invfact[i] = MOD - ((MOD / i) * invfact[MOD % i]) % MOD;
	}
	for (int i = 2; i < 200001; i++) {
		invfact[i] = (invfact[i] * invfact[i - 1]) % MOD;
	}
}

int N, M;
int parent[200001];
vector<int> G[200001];

pair<ll, ll> dfs(int cur, int par) { // {경우의 수, cur을 루트로 갖는 subtree의 노드 개수}
	ll ret = 1;
	ll childcnt = 0;
	for (auto& nxt : G[cur]) {
		if (nxt == par) continue;
		auto tmp = dfs(nxt, cur);
		ret = (ret * tmp.first) % MOD;
		ret = (ret * invfact[tmp.second]) % MOD;
		childcnt += tmp.second;
	}
	
	ret = (ret * fact[childcnt]) % MOD;
	return make_pair(ret, childcnt + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	init();

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		parent[y] = x;
	}

	for (int i = 1; i <= N; i++) G[parent[i]].emplace_back(i);

	cout << dfs(0, -1).first;
}