首页 > 代码库 > bzoj-3444 3444: 最后的晚餐(组合数学)
bzoj-3444 3444: 最后的晚餐(组合数学)
题目链接：
3444: 最后的晚餐
Description
【问题背景】
高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。
【问题描述】
饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输出方案总数取余989381的值，也可能为0）。
Input
输入有m+1行，第一行有两个用空格隔开的正整数n、m，如题所示。接下来的m行，每一行有两个用空格隔开的正整数，第i行为Ai和Bi，表示Ai的暗恋对象为Bi，保证Ai互不相等。
Output
输出只有一行，这一行只有一个数字，如题所示。
Sample Input
4 2
1 2
4 3
1 2
4 3
Sample Output
8
题意：
思路：
只有单链和点才满足要求,分叉和环都不能有;链有两个方向放所以ans=(l+r)!*2^l;l为链的个数,r为点的个数;
AC代码：
/************************************************************** Problem: 3444 User: LittlePointer Language: C++ Result: Accepted Time:6100 ms Memory:67784 kb****************************************************************/ #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bits/stdc++.h>#include <stack>#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<‘0‘||CH>‘9‘;F= CH==‘-‘,CH=getchar()); for(num=0;CH>=‘0‘&&CH<=‘9‘;num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);} const LL mod=989381;const double PI=acos(-1.0);const int inf=1e9;const int N=5e5+20;const int maxn=1e4+220;const double eps=1e-12; int n,m,in[N],p[N],sum[N],num,vis[N];vector<int>ve[N];int findset(int x){ if(x==p[x])return x; return p[x]=findset(p[x]);}inline void same(int x,int y){ int fx=findset(x),fy=findset(y); if(fx!=fy) { p[fx]=fy; sum[fy]+=sum[fx]; sum[fx]=0; }} map<int,int>mp[N];void dfs(int cur,int fa){ vis[cur]=1; num++; int len=ve[cur].size(); for(int i=0;i<len;i++) { int temp=ve[cur][i]; if(temp==fa)continue; dfs(temp,cur); }}int check(){ for(int i=1;i<=n;i++) { if(in[i]>2)return 0; } num=0; for(int i=1;i<=n;i++) { if(!vis[i]) { if(in[i]==0)vis[i]=1,num++; else if(in[i]==1)dfs(i,0); } } if(num!=n)return 0; return 1;}LL pow_mod(int y){ LL s=1,base=2; while(y) { if(y&1)s=s*base%mod; base=base*base%mod; y>>=1; } return s;}int main(){ //freopen("in.txt","r",stdin); read(n);read(m); for(int i=0;i<=n;i++)p[i]=i,sum[i]=1; int u,v; For(i,1,m) { read(u);read(v); if(mp[v][u])continue; ve[u].push_back(v); ve[v].push_back(u); same(u,v); in[u]++; in[v]++; mp[u][v]=1; } LL ans=0; if(check()) { ans=1; int l=0,r=0; for(int i=1;i<=n;i++) { if(p[i]!=i)continue; if(sum[i]>1)l++; else r++; } for(int i=1;i<=l+r;i++)ans=ans*(LL)i%mod; ans=ans*pow_mod(l)%mod; } cout<<ans<<endl; return 0;}
bzoj-3444 3444: 最后的晚餐(组合数学)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。