BZOJ3444: 最后的晚餐

3444: 最后的晚餐

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 234 Solved: 80
[Submit][Status]

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

Sample Output

8

【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。

HINT

Source

By lll6924 at“酱油杯noi考后欢乐赛”

题解：
有些题目是你不愿意去想，仔细想想还是十分简单的。
对于此题来说，我们对n个点构造一张无向图，暗恋关系理解为双向边，显然如果某个点的度数>2那么误解，或者有环那么无解。
有解的话，就是一下连通分量，并且这些连通分量都是一条链，然后这些链之间是独立的，我们就可以全排列了。
然后如果连通分量内的点数>1的话左右是不一样的，ans还要*2
注意可能出现重边
代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 500000+5
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 989381
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 int n,m,fa[maxn],inp[maxn],s[maxn];
61 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
62 map<pa,int>mp;
63 
64 int main()
65 
66 {
67 
68     freopen("input.txt","r",stdin);
69 
70     freopen("output.txt","w",stdout);
71 
72     n=read();m=read();
73     for1(i,n)fa[i]=i;
74     for1(i,m)
75     {
76         int x=read(),y=read(),xx=find(x),yy=find(y);
77         if(mp[pa(x,y)]||mp[pa(y,x)])continue;
78         mp[pa(x,y)]=mp[pa(y,x)]=i;
79         inp[x]++;inp[y]++;
80         if(inp[x]>2||inp[y]>2||xx==yy){cout<<0<<endl;return 0;}
81         fa[xx]=yy;
82     }
83     ll cnt1=0,cnt2=0,ans=1;
84     for1(i,n)s[find(i)]++;
85     for1(i,n)
86      if(fa[i]==i)
87       {
88         cnt1++;
89         ans=ans*cnt1%mod;
90         if(s[i]!=1)cnt2++;
91       }        
92     for1(i,cnt2)ans=ans*2%mod;    
93     cout<<ans<<endl;
94 
95     return 0;
96 
97 }

View Code