BZOJ3444: 最后的晚餐

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

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

把暗恋关系看作双向边，如果所有点度数都<=2，且没有环则有解。

否则不难发现每个连通分量是一条链，如果链上元素多于1则答案是2，否则答案是1。

每个连通分量肯定在一起，所以再将答案乘以连通分量个数的阶乘就行了。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cmath>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=<<;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,,BufferSize,stdin);

        tail=(head=buffer)+l;

    }

    return *head++;

}

inline int read() {

    int x=,f=;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=Getchar()) x=x*+c-'';

    return x*f;

}

typedef long long ll;

const int mod=;

const int maxn=;

int n,m,A[maxn],in[maxn],pa[maxn];

int findset(int x) {return pa[x]==x?x:pa[x]=findset(pa[x]);}

int main() {

     n=read();m=read();

     rep(i,,n) pa[i]=i;

     rep(i,,m) {

        int u=read(),v=read();

        if(A[v]==u) continue;

        if(findset(u)==findset(v)) {puts("");return ;}

        pa[findset(u)]=findset(v);

        in[v]++;in[u]++;A[u]=v;

    }

    int ok=,blo=;

    rep(i,,n) {

        if(in[i]>) ok=;

        if(findset(i)==i) blo++;

    }

    if(!ok) puts("");

    else {

        ll ans=,cnt=;

        rep(i,,blo) (ans*=i)%=mod;

        rep(i,,n) if(!in[i]) cnt++;

        rep(i,,blo-cnt) (ans*=)%=mod;

        printf("%lld\n",ans);

    }

    return ;

}

秒客网