/*
给定n头牛，m个谷仓，每头牛只能在一些特定的谷仓，一个谷仓只能有一头牛
问可行的安排方式
dp[i][j]表示前i头牛组成状态j的方案数，状态0表示无牛，1表示有牛
使用滚动数组即可
枚举到第i头牛时，状态j必须有i-1头牛，然后由这个状态推导出第i头牛的状态，再清0
*/
#include<iostream>
#include<cstring>
using namespace std;
int n,m,k,mp[
25][
25],dp[
1<<
21],tmp;
int main(){
while(cin>>n>>
m){
memset(dp,0,
sizeof dp);
memset(mp,0,
sizeof mp);
for(
int i=
1;i<=n;i++
){
cin>>
k;
while(k--
)
cin>>tmp,mp[i][tmp]=
1;
}
dp[0]=
1;
for(
int i=
1;i<=n;i++
)
for(
int j=(
1<<m)-
1;j>=
0;j--){
//这里是由状态j推出别的状态，即由牛少的状态推出牛多的状态，所以此处必须从大到小枚举状态！
if(dp[j]==
0)
continue;
//状态j必须有i-1头牛，即必须大于0
for(
int k=
1;k<=m;k++
)
if(mp[i][k]&&j!=(j|(
1<<(k-
1))))
//第i头牛可以放在k这个位置
dp[j|(
1<<(k-
1))]+=
dp[j];
dp[j]=
0;
}
int ans=
0;
for(
int j=(
1<<m)-
1;j>=
0;j--
)
ans+=
dp[j];
printf("%d\n",ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10358474.html
