HDU5399-多校-模拟

Too Simple

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1214    Accepted Submission(s): 406

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

3 3
1 2 3
-1
3 2 1

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.

一开始看起来很复杂，想了想发现只要保证最后一个函数是任意的，中间的其他函数都没问题。

但是有一个坑的情况是，可能一个任意函数也没有，全都是固定的函数，这时要验证这组函数是否可行。我们当时验证的顺序弄反，卡了一场，真是too simple。

最近做的题都是模拟题啊，，，太没技术含量了，，，，

 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <ctype.h>
 #include <cstdlib>
 #include <stack>
 #include <set>
 #include <map>
 #include <queue>
 #include <string>
 #include <cmath>

 using namespace std;
 const long long MOD = 1e9+;

 int N,T,M;
 int func[][],vis[];
 long long nn;

 long long qpow(long long a,long long i,long long n)
 {
     if(i == ) return  % n;
     long long temp = qpow(a,i>>,n);
         temp = temp * temp % n;
     if( i& ) temp = temp * a % n;
     return temp;
 }

 long long mi(long long a,int t)
 {
     long long ans = ;
     for(int i=;i<t;i++) {ans *= a;ans %= MOD;}
     return ans;
 }

 long long solve()
 {
     for(int i=;i<=N;i++)
     {
         int ans = i;
         for(int j=M-;j>=;j--)
         {
             ans = func[j][ans-];
         }
         if(ans != i) return 0LL;
     }
     return 1LL;
 }

 int main()
 {
     while(~scanf("%d%d",&N,&M))
     {
         long long cnt = 0LL,ans = 0LL;
         nn = 1LL;
         int flag = ;
         for(int i=; i <= N;i++) {nn *= i; nn %= MOD;}

         for(int i=;i<M;i++)
         {
             memset(vis,,sizeof vis);
             if(scanf("%d",&func[i][]) && (func[i][] == -))
             {
                 cnt++;
             }
             else
             {
                 vis[func[i][]]++;
                 for(int j=;j<N;j++)
                 {
                     scanf("%d",&func[i][j]);
                     if( vis[func[i][j]] ) flag = ;
                     else vis[func[i][j]]++;
                 }
             }
         }

         if(flag) ans = 0LL;
         else if(cnt > ) { ans = mi(nn,cnt-); ans %= MOD;}
         else
         {
             ans = solve();
         }

         printf("%I64d\n",ans%MOD);
     }
 }