记录编号	420016	评测结果	AAAAAAAAAA
题目名称	棋盘放車	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2017-07-03 19:02:46	内存使用	16.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;

LL f[1<<20],n,tmp,m,un[30],cnt[1<<20];

void in(){
	freopen("examone.in","r",stdin);
	freopen("examone.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		un[a]|=1<<(n-b);
    }
	tmp=(1<<n)-1;
	for(LL i=1;i<=tmp;i++)
		cnt[i]+=cnt[i>>1]+(i&1);
}

LL lowbit(int x){
	return x&-x;
}

void dp(){
	f[0]=1;
	for(LL i=1;i<=tmp;i++){
		for(LL j=i;j;j-=lowbit(j)){
			LL k=lowbit(j);
			if(k&un[cnt[i]]) continue;
			f[i]+=f[i-k];
		}
	}
}

int main(){
	in();
	dp();
	printf("%lld",f[tmp]);
	return 0;
}