2441:Arrange the Bulls

問題文
http://poj.org/problem?id=2441

n頭の牛がいて、m棟の小屋がある。牛にはそれぞれ入れる小屋が決まっていて、全部の牛を小屋に入れるような入れ方が何通りあるかを求めよ。

ビットDPした。
dp[ 牛の番号 ][ どの小屋を使ったか ] := 場合の数

配列がとれなかったので遇奇で使い回した。
コード中のjとSのループを回す順番を逆にするとTLEする。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

int dp[2][1<<20],cow[21][21],p[21];

int main(void){

  int n,m;
  scanf("%d %d",&n,&m);

  for(int i=1;i<=n;i++){
    scanf("%d",&p[i]);
    for(int j=0;j<p[i];j++)scanf("%d",&cow[i][j]);
  }
  
  dp[0][0]=1;
  for(int i=1;i<=n;i++){
    for(int j=0;j<p[i];j++){
      for(int S=0;S<(1<<m);S++){
	if(S>>(cow[i][j]-1)&1)dp[i&1][S]+=dp[(i-1)&1][S&~(1<<(cow[i][j]-1))];
      }
    }
    for(int j=0;j<(1<<m);j++)dp[(i-1)&1][j]=0;
  }

  int ans=0;
  for(int i=0;i<(1<<m);i++)ans+=dp[n&1][i];
  cout << ans << endl;

  return 0;
}