首页 > 代码库 > ZOJ 3687

ZOJ 3687

2024-07-25 06:52:58   221人阅读

赤裸的带禁区的排列数，不过，难点在于如何用程序来写这个公式了。纠结了好久没想到，看了看别人的博客，用了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;}

　　

ZOJ 3687


联系
我们