Too Simple

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 789 Accepted Submission(s): 267

Problem Description

Rhason Cheung had a simple problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help.

Teacher Mai has m functions f1,f2,⋯,fm:{1,2,⋯,n}→{1,2,⋯,n}(that
means for all x∈{1,2,⋯,n},f(x)∈{1,2,⋯,n}).
But Rhason only knows some of these functions, and others are unknown.

She wants to know how many different function series f1,f2,⋯,fm there
are that for every i(1≤i≤n),f1(f2(⋯fm(i)))=i.
Two function series f1,f2,⋯,fm and g1,g2,⋯,gm are
considered different if and only if there exist i(1≤i≤m),j(1≤j≤n),fi(j)≠gi(j).

Input

For each test case, the first lines contains two numbers n,m(1≤n,m≤100).

The following are m lines.
In i-th
line, there is one number −1 or n space-separated
numbers.

If there is only one number −1,
the function fi is
unknown. Otherwise the j-th
number in the i-th
line means fi(j).

Output

For each test case print the answer modulo 109+7.

Sample Input

Sample Output

1

Hint

The order in the function series is determined. What she can do is to assign the values to the unknown functions.

Author

xudyh

Source

2015 Multi-University Training Contest 9

/* ***********************************************

Author        :CKboss

Created Time  :2015年08月19日 星期三 10时25分44秒

File Name     :HDOJ5399.cpp

************************************************ */

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstdlib>

#include <vector>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long int LL;

const LL mod=1e9+7LL;

const int INF=50000000;

int n,m;

int f[110][110];

int cn;

int color[110];

bool COLOR(int x,int c)

{

	if(color[x]==c) return false;

	color[x]=c; cn++;

	return true;

}

LL QuickPow(LL a,LL n)

{

	LL e=1;

	while(n)

	{

		if(n&1) e=(a*e)%mod;

		a=(a*a)%mod;

		n/=2;

	}

	return e%mod;

}

bool used[110];

LL jc(LL n)

{

	LL ret=1;

	for(int i=2;i<=n;i++)

		ret=(ret*i)%mod;

	return ret%mod;

}

bool check_P(int x,int L=1,int R=m)

{

	if(used[x]==true) return false;

	int nx=x;

	for(int i=R;i>=L;i--)

	{

		nx=f[i][nx];

	}

	if(nx==x)

	{

		if(used[x]==false)

		{

			used[x]=true;

			return true;

		}

		else return false;

	}

	return false;

}

bool check_Range(int L,int R)

{

	memset(used,false,sizeof(used));

	bool flag=true;

	for(int i=1;i<=n&&flag;i++)

	{

		int nx=i;

		for(int j=R;j>=L;j--)

		{

			nx=f[j][nx];

		}

		if(used[nx]==true) return false;

		else used[nx]=true;

	}

	return true;

}

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	while(scanf("%d%d",&n,&m)!=EOF)

	{

		int nig=0;

		bool check=true;

		memset(color,0,sizeof(color));

		for(int i=1;i<=m;i++)

		{

			scanf("%d",&f[i][1]);

			if(f[i][1]==-1) nig++;

			else

			{

				cn=0;

				check=COLOR(f[i][1],i);

				for(int j=2;j<=n;j++)

				{

					scanf("%d",&f[i][j]);

					check=COLOR(f[i][j],i);

				}

				if(cn!=n) check=false;

			}

		}

		if(check==false)

		{

			puts("0");

		}

		else if(check&&nig==0)

		{

			/// tePan

			memset(used,false,sizeof(used));

			bool flag=true;

			for(int i=1;i<=n&&flag;i++)

			{

				if(check_P(i)==false) flag=false;

			}

			if(flag==true) puts("1");

			else puts("0");

		}

		else

		{

			//// (n!^(nig-1))

			bool flag=true;

			int Left=INF,Right=-INF;

			f[m+1][1]=-1;

			for(int i=1;i<=m+1&&flag;i++)

			{

				if(f[i][1]==-1)

				{

					if(Left!=INF&&Right!=-INF)

					{

						/// check;

						flag=check_Range(Left,Right);

					}

					Left=INF; Right=-INF;

				}

				else

				{

					Left=min(Left,i); Right=max(Right,i);

				}

			}

			if(flag==false) puts("0");

			else printf("%lld\n",QuickPow(jc(n),nig-1)%mod);

		}

	}

    return 0;

}

巴特西

HDOJ 5399 Too Simple

Too Simple

最新文章

热门文章