首页 > 代码库 > ZOJ 3687
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;}
ZOJ 3687
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。