记录编号	175764	评测结果	AAAAAAAAAA
题目名称	[POJ2441]安排公牛	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.269 s
提交时间	2015-08-07 00:34:50	内存使用	6.16 MiB

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

const int MAXSTATE=(1<<20);
int bull_num[MAXSTATE];//二进制一个状态下多少头牛
vector <int> state[21];//状态[公牛数][第几个]
int re_state[MAXSTATE];//状态在适当公牛数下第几个
unsigned int func[MAXSTATE];//方案数[状态]
int N,M,P;
int lowbit(int X) { return X&(-X); }

int temp[21];
	
int S;

void BFS(int step)
{
	if(step==1)
	{
		for(int i=1;i<=P;i++)
			func[1<<(temp[i]-1)]=1;
		//for(int i=0;i<S;i++)printf("%d %d\n",i,func[i]);
		return;
	}//第一头公牛
	for(unsigned int i=0;i<state[step-1].size();i++)
	{
		if(func[state[step-1][i]]==0)continue;
		int temp_state=state[step-1][i];
		for(int j=1;j<=P;j++)
		{
			//int temp_location = 1<<(temp[j]-1);
			if( (temp_state >> ( temp[j] - 1 ) ) % 2 == 0 )//空位
			{
				func[temp_state+(1<<(temp[j]-1))]+=func[temp_state];
			}
		}
	}
	//for(int i=0;i<S;i++)printf("%d %d\n",i,func[i]);
}

int main()
{
	freopen("examnine.in","r",stdin);
	freopen("examnine.out","w",stdout);
	scanf("%d %d",&N,&M);
	
	S=(1<<M);
	
	memset(func,0,sizeof(func));
	
	bull_num[0]=0;
	for(int i=1;i<S;i++)
		bull_num[i]=bull_num[i-lowbit(i)]+1;
	for(int i=1;i<S;i++)
	{
		state[bull_num[i]].push_back(i);
		re_state[i]=state[bull_num[i]].size()-1;
	}
	//for(int i=0;i<=S;i++)printf("%d %d\n",i,bull_num[i]);
	
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&P);
		for(int j=1;j<=P;j++)scanf("%d",&temp[j]);
		BFS(i);
	}
	
	//for(int i=0;i<S;i++)printf("%d %d\n",i,func[i]);
	
	unsigned int ans=0;
	for(int i=0;i<state[N].size();i++)
		ans+=func[state[N][i]];
	printf("%d\n",ans);
	return 0;
}