ABC041 D: 徒競走

問題

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
の順列を考える。数 は、数 の前にあるという情報が 個与えられる。条件を満たす順列の総数を求めよ。

• 
• のペアはすべて相異なる。
• 全ての情報に合致する並びが少なくとも1つ存在する。

解法

全探索はで間に合わないため、bitDPをして とする。

dp[使った要素の集合][最後に使った要素] := 順列の総数

として数え上げる。任意の使ってない要素に対して、最後に使った要素より先に来るような情報がある場合、そのような順列は数えてはならない。

またこの問題は、半順序関係に対応する全順序関係を数え上げる問題になるので、DAGについてトポロジカルソートの総数を求める問題といえる。以下のPDFの5ページ目が参考になる。http://www-erato.ist.hokudai.ac.jp/docs/autumn2013/inoue.pdf

ll dp[1<<16][16];
int N, M;
int G[16][16];
 
ll dfs(int S, int x) {
 
  if(S == (1<<N) - 1) return 1;
 
  ll& ret = dp[S][x == -1 ? 0 : x];
  if(~ret) return ret;
 
  ret = 0;
  rep(y, N)
    if(!(S >> y & 1)) {
      if(x == -1 || G[y][x] <= 0)
        ret += dfs(S | 1 << y, y);
      else
        return ret = 0;
    }
 
  return ret;
}
 
int main() {
 
  cin >> N >> M;
  minus(G);
  rep(i, M) {
    int x, y; cin >> x >> y;
    x--, y--;
    G[x][y] = 1;
    G[y][x] = 0;
  }
 
  minus(dp);
  cout << dfs(0, -1) << endl;
  
  return 0;
}