POJ.2441 Arrange the Bulls

1.Problem
http://poj.org/problem?id=2441

2.Idea
bit DP

3.Source

 int N, M;  
 int cows[22][22];  
 int dp[1 << 20 + 1];  
 int solve(int i, int S)  
 {  
      if (dp[S] != -1) return dp[S];  
      if (i == N) return 1;  
      int res = 0;  
      for (int k = 0; k < M; k++) {  
           if (cows[i][k] && !((1 << k) & S)) {  
                res += solve(i + 1, S | (1 << k));  
           }  
      }  
      return dp[S] = res;  
 }  
 int main()  
 {  
      memset(dp, -1, sizeof dp);  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) {  
           int p;  
           cin >> p;  
           for (int j = 0; j < p; j++) {  
                int t;  
                cin >> t;  
                cows[i][t - 1] = 1;  
           }  
      }  
      cout << solve(0, 0) << endl; // i-th cow, current mask  
      return 0;  
 }