読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 040

abc040.contest.atcoder.jp

解説を勉強してみた
トポロジカルソートの場合の数の算出をbitDPを用いてO(n!)をO(m2^n)にする問題
f(S)=\{(頂点集合Sとおいた時のルートの要素数)\}
とおけば以下の漸化式で求まる
f(S)=\sum_{v\in X_S} f(S-\{v\})
ただし
X_S=\{v\in S|vからS-{v}への辺が存在しない\}
集合をbit列で表し小さい方から順に足し合わせれば良い

int g[16][16];
ll dp[1<<16];

int main()
{
  int n,m; cin>>n>>m;
  REP(i,m)
  {
    int x,y;cin>>x>>y;
    g[x-1][y-1]=1;
  }
  dp[0]=1;
  REP(i,1<<n)
  {
    REP(j,n)if(!(i>>j&1))
    {
      bool f=true;
      REP(k,n)if(i>>k&1&&g[j][k]){f=false;break;}
      if(f)dp[i|1<<j]+=dp[i];
    }
  }
  cout<<dp[(1<<n)-1]<<endl;
}