BOJ 1742 레이싱 결과

* BOJ 1742 레이싱 결과

[분류 : 다이나믹 프로그래밍, DAG, 그래프 이론, 조합론]

[풀이]

  1. [그래프 구조] 먼저 구성되는 컴포넌트의 구조는 양방향 그래프가 아닌 DAG(Directed Acyclic Graph)이어야 한다. 즉, 사이클이 존재하면 모순이 발생하므로 경우의 수는 0이 돼야 한다.

  2. [컴포넌트 집합] 하나의 컴포넌트에 여러 노드가 존재할 수 있다. 따라서 같은 컴포넌트에 있는 노드를 집합으로 둔다.

  3. [진출 간선?] 나는 경기결과를 작성할 때 맨 뒤에서 시작해서 작성하는 걸 채택했다. 구성되는 dag 컴포넌트에서 진출 간선이 0인 것들부터 넣는 방식을 생각해보자. 진출 간선이 없다는 의미는 더 이상 자신이 반드시 이기는 상대가 존재하지 않는다는 뜻이다.

  따라서 리프(Leaf) 노드부터 사용해나가면서 자신 부모의 진출 간선 수를 정확히 하나만 줄여주고 그 부모 진출 간선이 0이 되면 다음 위치에서 사용할 수 있도록 구성해주는 것이다

  4. [여러 개의 컴포넌트] i번 컴포넌트를 계산했다고치고 그 경우의 수를 라고 하자. 또 그 컴포넌트를 이루는 노드의 수를 라면 정답은 아래 수식으로 표현할 수 있다

N개의 수를 나열해놓고 중복을 제거하는 간단한 수식이다.

  5. [다이나믹 프로그래밍] 이제 값을 어떻게 계산하는지, 먼저 dp 형태를 생각해보자. 같은 컴포넌트에 대해서 진행되어야함을 생각하시고..

(1) 현재 위치

(2) 사용할 수 있는 노드 집합

  위치야 30밖에 되지 않지만 집합이 문제다. 비트셋으로 표현하자니 2^30의 크기가 부담스럽고 set이나 vector로 처리하기엔 여간 까다로운게 아니다. 그래서 그냥 비트셋 + map으로 쓰면 편하다.

  (다이나믹 판단 여부) 편의상 DAG가 이진 트리를 이루고 있다고 가정해보자. 이진 트리에서 가장 왼쪽 노드와 중간 노드를 각각 A, B로 둘 때, 순서를 A->B 순으로 사용할 때와 B->A로 사용하는 경우를 생각할 때 그 다음 단계에서 사용할 수 있는 노드 집합은 정확히 똑같다. 또한 다음 단계에서도 똑같은 문제를 가지고 있으며 문제 크기가 작아졌기에 최적 부분 구조를 가지고 있으며 A->B와 B->A 순 배치에 대해 같은 부분 문제를 풀어야하므로 부분 문제가 중복되기에 다이나믹 프로그래밍 이 적합하다.

  아래 그림 빨간 노드는 현재 사용할 수 있는 노드, 흰색은 사용하지 않은 노드 중에서 현재 사용할 수 없는 노드, 회색은 사용된 노드를 의미한다.

그림1 : DAG 예시. 현재 사용할 수 있는 노드는 5개(A, B, 1, 2, 4)	그림2 : A->B 또는 B->A순으로 삭제했을 때 그래프

  6. [Modulo inverse] 마지막으로 페르마의 소정리를 이용하여 분모부분을 해결해주면 되시겠다.

#include<cstdio>
#include<vector>
#include<unordered_map>
using namespace std;
using ll = long long;
const int MAX_N = 30, MOD = 1e6 + 3;
struct _d { int v, c; };
vector<int> adj[MAX_N], radj[MAX_N];
int N, f[MAX_N], outd[MAX_N], fac[MAX_N + 1] = { 1 };
unordered_map<int, int> dp;
int _pow(int a, int n) {
	if (n <= 1) return n ? a : 1;
	int h = _pow(a, n >> 1);
	return ((ll)h * h % MOD) * (n % 2 ? a : 1) % MOD;
}
int dfs(int u) {
	int r = 1;
	f[u] = 1;
	for (int& v : adj[u]) {
		if (f[v]) r &= f[v] == 2;
		else r &= dfs(v);
	}
	f[u] = 2;
	return r;
}
_d dfs2(int u) {
	_d r = { adj[u].empty() ? (1 << u) : 0, 1 };
	f[u] = 3;
	for (int& v : adj[u]) if (f[v] != 3) {
		_d c = dfs2(v);
		r.v |= c.v;
		r.c += c.c;
	}
	for (int& p : radj[u]) if (f[p] != 3) {
		_d c = dfs2(p);
		r.v |= c.v;
		r.c += c.c;
	}
	return r;
}
int rec(int s) {
	if (!s) return 1;
	auto it = dp.find(s);
	if (it != dp.end()) return it->second;
	int& ret = dp[s], i, ts;
	for (i = 0; i < N; i++) if ((1 << i) & s) {
		ts = s ^ (1 << i);
		for (int& p : radj[i]) {
			outd[p]--;
			if (!outd[p]) ts |= (1 << p);
		}
		ret = (ret + rec(ts)) % MOD;
		for (int& p : radj[i])
			outd[p]++;
	}
	return ret;
}
int main() {
	int M, u, v, valid = 1, i;
	ll ans = 0;
	for (i = 1; i <= MAX_N; i++) fac[i] = (ll)i * fac[i - 1] % MOD;

	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		adj[u].push_back(v);
		radj[v].push_back(u);
		outd[u]++;
	}
	for (i = 0; i < N; i++) if (!f[i])
		valid &= dfs(i);
	if (valid) {
		ans = 1;
		for (i = 0; i < N; i++) if (f[i] != 3) {
			_d s = dfs2(i);
			ans = ans * rec(s.v) % MOD;
			ans = ans * _pow(fac[s.c], MOD - 2) % MOD;
		}
		ans = ans * fac[N] % MOD;
	}
	printf("%lld", ans);
	return 0;
}