记录编号	47022	评测结果	AAAAAAAAAA
题目名称	棋盘放車	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.659 s
提交时间	2012-10-30 11:32:42	内存使用	12.28 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <stack>
using namespace std;

int una[21];
unsigned long long f[1048575];
bool insta[1048575];
stack<int> sta,stanew,staempty;

int lowbit(int num)
{
	return((-num)&(num));
}

int main(void)
{
	freopen("examone.in","r",stdin);
	freopen("examone.out","w",stdout);
	int i,j,n,m,a,b,full,ava,pos,temp;
	unsigned long long total=0;
	cin>>n>>m;
	full=(1<<n)-1;
	for (i=1;i<=m;i++)
	{
		cin>>a>>b;
		una[a]=una[a]+(1<<(b-1));
	}
	for (j=1;j<=full;j<<=1)
	{
		if (((~una[1])&j)!=0)
		{
			f[j]=1;
			stanew.push(j);
		}
	}
	for (i=2;i<=n;i++)
	{
		memset(insta,0,sizeof(insta));
		sta=stanew;
		stanew=staempty;
		while (!sta.empty())
		{
			a=sta.top();
			ava=(~a)&(~una[i])&full;
			while (ava)
			{
				pos=lowbit(ava);
				ava-=pos;
				temp=pos|a;
				f[temp]+=f[a];
				if (!insta[temp])
				{
					insta[temp]=true;
					stanew.push(temp);
				}
			}
			sta.pop();
		}
	}
	while (!stanew.empty())
	{
		temp=stanew.top();
		total+=f[stanew.top()];
		stanew.pop();
	}
	cout<<total<<endl;
	return(0);
}