ZOJ 3687

赤裸的带禁区的排列数，不过，难点在于如何用程序来写这个公式了。纠结了好久没想到，看了看别人的博客，用了DFS，实在妙极，比自己最初想用枚举的笨方法高明许多啊.\

http://blog.csdn.net/hlmfjkqaz/article/details/11037821

自己理解那个DFS后自己敲的。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const LL MOD=55566677;

bool visr[55],visc[55];

bool cant[55][55];

int ban[30][2];

LL f[55];

LL ans;

int n,m;

void initial(){

	f[0]=1;

	for(LL i=1;i<55;i++)

	f[i]=(f[i-1]*i)%MOD;

}

void dfs(int i,int num){    //禁止位置公式求法，实在是妙极地运用了DFS啊，只好

								//学习一下了

	if(i>=m){

		if(num&1) ans=((ans-f[n-num])%MOD+MOD)%MOD;

		else ans=(ans+f[n-num])%MOD;

		return ;

	}

	dfs(i+1,num);

	if(!visr[ban[i][0]]&&!visc[ban[i][1]]){

		visr[ban[i][0]]=visc[ban[i][1]]=true;

		dfs(i+1,num+1);

		visr[ban[i][0]]=visc[ban[i][1]]=false;

	}

}

int main(){

	initial();

	while(scanf("%d%d",&n,&m)!=EOF){

		memset(visc,false,sizeof(visc));

		memset(visr,false,sizeof(visr));

		memset(cant,false,sizeof(cant));

		for(int i=0;i<m;i++){

			scanf("%d%d",&ban[i][0],&ban[i][1]);

			if(cant[ban[i][0]][ban[i][1]]){

				i--;

				m--;

			}

			else

			cant[ban[i][0]][ban[i][1]]=true;

		}

		ans=0;

		dfs(0,0);

		printf("%lld\n",ans);

	}

	return 0;

}