Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

12/25
17:24
乱搞

[bzoj 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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

s1是单点个数,s2是链的个数,答案就是2^s2*(s1+s2)!

根据每个点的度数和dfs判环来判断有没有解,注意重边

 

[bzoj 3444] 最后的晚餐