In Chinese Restaurant

题目连接：

http://acm.hust.edu.cn/vjudge/contest/123332#problem/B

Description

When Vova arrived in Guangzhou, his Chinese friends immediately invited him to a restaurant. Overall n people came to the restaurant, including Vova. The waiter offered to seat the whole company at a traditional large round table with a rotating dish plate in the center.

As Vova was a guest, he got the honorable place by the door. Then m people in the company stated that they wanted to sit near a certain person. Your task is to determine the number of available arrangements to seat Vova's friends at the table.

Input

The first line contains integers n and m (2 ≤ n ≤ 100; 0 ≤ m ≤ n). The next m lines contain integers k1, …, km, where ki is the number of the person who the person number i wants to sit with (1 ≤ ki ≤ n; ki ≠ i). Being an honorable guest, Vova got number 1. His friends are numbered with integers from 2 to n.

Output

Print the number of available arrangements to seat Vova's friends modulo 10 9 + 7.

Sample Input

6 6

2

1

1

5

6

5

Sample Output

4

Hint

题意

有n个人在坐在一个圆桌上，给你m个关系a,b,表示a要挨着b坐

问你有多少个方案数

题解：

如果出现环，答案为2，否则就是全排列乘以2

特判掉 只有两个人的情况，因为这样正着坐和反着坐答案是一样的。

代码

#include <bits/stdc++.h>

#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))

#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))

#define pb push_back

#define mp make_pair

#define sf scanf

#define pf printf

#define two(x) (1<<(x))

#define clr(x,y) memset((x),(y),sizeof((x)))

#define dbg(x) cout << #x << "=" << x << endl;

const int mod = 1e9 + 7;

int mul(int x,int y){return 1LL*x*y%mod;}

int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

using namespace std;

const int maxn = 1e3 + 15;

vector<int>G[maxn],block[maxn];

int n , m ,vis[maxn] , c[maxn],tot,sz[maxn],deg[maxn],fac[maxn],C[maxn][maxn],moo[maxn][maxn];

set < int > Edge[maxn];

void maintain(int & x){

    if( x >= mod ) x-= mod;

}

bool dfs1( int x , int pre ){

	c[x] = 1;

	for(auto v:G[x]){

		if( v == pre ) continue;

		if(c[v] == 1) return true;

		else if(c[v] == 0){

			if(dfs1(v,x)) return true;

		}

	}

	c[x] = 2;

	return false;

}

void predfs( int x ){

	block[tot].pb( x );

	for(auto v : G[x])

		if( vis[v] == 0 ){

			vis[v] = 1;

			predfs( v );

		}

}

void init(){

	fac[0] = 1;

	C[0][0] = 1;

	rep(i,1,maxn-1){

		fac[i] = mul( fac[i - 1] , i );

		C[i][0] = 1;

		rep(j,1,i){

			C[i][j] = C[i][j - 1] + C[i - 1][j - 1] ;

			maintain( C[i][j] );

		}

	}

}

int main(int argc,char *argv[]){

	init();

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

	if(n == 2 && m >= 1 ){

		pf("1\n");

		return 0;

	}

	rep(i,1,n) G[i].clear();

	rep(i,1,m){

		int v=read();

		Edge[i].insert( v );

		moo[i][v]=moo[v][i]=1;

	}

	rep(i,1,n){

		rep(j,1,n) if( moo[i][j]  && i != j ) G[i].pb( j );

	}

	int ok = 0;

	rep(i,1,n) if(c[i] == 0){

		if( dfs1( i , 0 ) ){

			ok = 1;

			break;

		}

	}

	rep(i,1,n) if(!vis[i]){

		vis[i]=1;

		++ tot;

		predfs( i );

	}

	// 有三条边或以上

	rep(i,1,n){

		int kk = 0;

		rep(j,1,n) if( moo[i][j]) ++ kk;

		if( kk > 2 ){

			pf("0\n");

			return 0;

		}

	}

	if( ok ){

		if( tot == 1 ){

			int judge = 1;

			rep(i,1,n) if(c[i] != 1) judge = 0;

			if( judge == 1 ) pf("%d\n" , 2);

			else pf("0\n");

		}else pf("0\n");

		return 0;

	}else{

		int ptr = 0 ;

		rep(i,1,tot){

			for(auto it : block[i]){

				if( it == 1 ){

					ptr = i;

				}

			}

		}

		int ans = 1 ;

		if( block[ptr].size() > 1 ) ans = 2;

		rep(i,1,tot){

			if( i == ptr ) continue;

			int cap = block[i].size();

			if( cap > 1 ) ans = mul( ans , 2 );

		}

		ans = mul( ans , fac[ tot - 1 ] );

		pf("%d\n" , ans );

	}

	return 0;

}

URAL 1962 In Chinese Restaurant 数学的相关教程结束。