Description

农夫约翰逊的公牛队非常喜欢打篮球。但是他们都不愿意和其他公牛一起打篮球，因为他们相信其他人都很虚弱。农民约翰逊有N头牛(我们把牛的数量从1到N)和M谷仓(我们把谷仓的编号从1到M)，这是他的公牛的篮球场。然而，他的公牛都很挑剔，他们只喜欢在一些特定的谷仓里玩耍，不想和其他的人共用一个谷仓。

因此，农民约翰逊很难安排他的公牛，他想让你帮助他。当然，找到一个解决方案很容易，但是您的任务是找到有多少个解决方案。

你应该知道，解决方案是这样一种情况：每头公牛都可以在他喜欢的谷仓里打篮球，没有两只公牛共用一个谷仓。

为了使问题变得简单一些，假定解决方案的数目不会超过10000000。

输入

在输入的第一行中，包含两个整数N和M(1<=N<=20，1<=M<=20)。接下来是N行。第一行首先包含一个整数P(1<=P<=M)，它指的是我喜欢玩的谷仓牛的数量。然后跟着P整数，给出P谷仓的数目。

输出

在一行中打印一个整数，这是解决方案的数量。

样本输入

3 4
2 1 4
2 1 3
2 2 4

样本输出

4

题解

状压dp
状态表示：
dp[i][s]:安排前i头奶牛，安排的篮球场为状态s的方案数。
第i层状态只与第i-1层状态有关，使用滚动数组优化。
用__builtin_popcount(s)函数来统计1的个数是否满足转移的条件。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=25;
bool cow[N][N];
int f[2][1<<20];
int n,m;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            cow[i][x-1]=true;
        }
    }

    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int s=0;s<(1<<m);s++)
            if(__builtin_popcount(s) == i-1)
                for(int j=0;j<m;j++)
                    if(!(s>>j & 1) && cow[i][j])
                        f[i&1][s|(1<<j)]+=f[i-1&1][s];

    int ans=0;
    for(int s=0;s<(1<<m);s++)
        if(__builtin_popcount(s) == n)
            ans+=f[n&1][s];

    cout<<ans<<endl;

    // system("pause");
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            cow[i][x-1]=true;
        }
    }

    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int s=0;s<(1<<m);s++)
        {
            if(f[i-1&1][s])//如果第i-1层状态满足
                for(int j=0;j<m;j++)
                    if(!(s>>j & 1) && cow[i][j])
                        f[i&1][s|(1<<j)]+=f[i-1&1][s];
            f[i-1&1][s]=0;//i-1层状态置零
        }

    int ans=0;
    for(int s=0;s<(1<<m);s++)
        ans+=f[n&1][s];

    cout<<ans<<endl;

    // system("pause");
}