Poj Solution 2441

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

//* @author: 
/*
  ����: 
   N��ţ��M�������(barn)��ÿ��ţ���м����Լ�ϲ����barn��Ҫ��Ϊÿ��ţ����һ��barn��
   ʹ��ÿ��ţ��ֵ���barn�����Լ�ϲ���ģ���ÿ��barn�v�ֻ������һ��ţ����Ϸ��ķ��䷽��������N,M<=20��

����:
  ��һ����N��M(1<=N<=20, 1<=M<=20);
  ����4��N��:
  ��i�еĵ�һ�������ǵ�i��ţϲ����barn��,���������ǵ�i��ţϲ����barn���(1<=i<=N)
���:
   ���䷽��������
*/
import java.util.*;
public class Main
{
 static final int N=20+2;
 static final int M=1<< 20+1;

 public static void main(String[] args){
   Scanner sc=new Scanner(System.in);
  int n, m, p;
   int mat[][]=new int[N][N];
   int dp[][]=new int[2][M];
   int i, k, j, next;
   n=sc.nextInt();
   m=sc.nextInt();
   for (i = 1; i <= n; i++)
   {
     p=sc.nextInt();
     while ((p--)!=0)
    {
     k=sc.nextInt();
     mat[i][k] = 1;
    }
  }

  int s = 0;
  dp[s][0] = 1;
  for (i = 1; i <= n; i++)
 {
   for (j = 0; j < (1 << m); j++) 
   {
     if (dp[s][j]!=0)
     { 
      for (k = 1; k <= m; k++)
      {
       if (mat[i][k] == 1)
       {
         next = j | (1 << (k - 1));
         if (next != j)      // ��k��barnû��ռ�� 
            dp[(s + 1) % 2][next] += dp[s][j];
       }
                                             
     }
    dp[s][j] = 0;
  }
 }

 s = (s + 1) % 2;
}
 int sum = 0;
 for (i = 0; i < (1 << m); i++) sum += dp[s][i];
      System.out.printf("%dn", sum);
}
}