徒競走 [ABC 041 : D]

問題

http://abc041.contest.atcoder.jp/tasks/abc041_d

N匹のうさぎが競争をした。
M人の観客が xi は yi よりも先にゴールしたと証言。
すべての観客の情報に合致するような着順が何通りあるか。

2 <= N <= 16
1 <= M <= N(N-1)/2

帰納的考察(Editorial見た)

1. N <= 16 とか O(2^N) 解法で確定やん
2. 数え上げ問題とかどうせbitDPでしょ
3. bitDP無理じゃない？トポロジカルソート？？？

―――― 壁 ――――

4. bitDPでした

bitDP
集合の有る無しを0と1で表現した、2進数で集合を表すやつを添え字にしたDP

5. dp[頂点集合Sをトポロジカルソートする方法の通り数]

トポロジカルソート
頂点集合の順列の部分集合で、どの2頂点をみても、後に来る頂点から先に来る頂点に有向辺が無いソーティング。
複数のソーティング結果が得られる場合もある

6. 大小関係を有向辺に見立てるというのはよくある手法
7. トポロジカルソートの数え上げはbitDPでできるらしい （知らんかった）
http://www-erato.ist.hokudai.ac.jp/docs/autumn2013/inoue.pdf
「トポロジカルソート 数え上げ」でググったらすぐ出た
困ったらググろう

実装

http://abc041.contest.atcoder.jp/submissions/790806

typedef long long ll;
int N, M;
 
ll dp[1 << 16];
bool bad[16][16];
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &N, &M);
	
	rep(i, 0, M) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--; y--;
		bad[y][x] = true;
	}
	
	dp[0] = 1;
	rep(i, 0, 1 << N) {
		rep(j, 0, N) if (!(i & (1 << j))) {
			bool ok = true;
			rep(k, 0, N) if (i & (1 << k)) if (bad[k][j]) ok = false;
			if (ok) dp[i + (1 << j)] += dp[i];
		}
	}
	cout << dp[(1 << N) - 1] << endl;
}