HDU 5399 Too Simple(過程中稍微用了一下dfs)——多校練習9

Too Simple

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

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.
   
        

題意：給你m個函數f1,f2,⋯,fm:{1,2,⋯,n}→{1,2,⋯,n}(即所有的x∈{1,2,⋯,n},對應的f(x)∈{1,2,⋯,n})，已知其中一部分函數的函數值，問你有多少種不同的組合使得所有的i(1≤i≤n),滿足f1(f2(⋯fm(i)))=i

對于函數集f1,f2,⋯,fm and g1,g2,⋯,gm，當且僅當存在一個i(1≤i≤m),j(1≤j≤n),fi(j)≠gi(j)，這樣的組合才視為不同。

如果還是不了解的話，我們來解釋一下樣例，

3 3

1 2 3

-1

3 2 1

樣例寫成函數的形式就是

n=3,m=3

f1(1)=1,f1(2)=2,f1(3)=3

f2(1)、f2(2)、f2(3)的值均未知

f3(1)=3,f3(2)=2,f3(3)=1

是以要使所有的i(1≤i≤n),滿足f1(f2(⋯fm(i)))=i，隻有一種組合情況，即f2(1)=3,f2(2)=2,f2(3)=1這麼一種情況

解題思路：其實，仔細想想，你就會發現，此題的解跟-1的個數有關，當隻有一個-1的時候，因為對應關系都已經決定了，是以隻有1種可行解，而當你有兩個-1時，其中一個函數的值可以根據另一個函數的改變而确定下來，故有n!種解。依此類推，當有k個-1時，解為

是以，我們隻需要提前将n！計算好取模存下來，剩下的就是套公式了

有一點需要提醒的是，當-1的個數為0時，即不存在-1的情況，解并不一定為0，若不存在-1的情況下仍滿足對于所有的i(1≤i≤n),滿足f1(f2(⋯fm(i)))=i，輸出1；否則輸出0，是以加個dfs判斷一下方案是否可行。多校的時候就被這一點坑了，看來還是考慮得不夠多。

若對上述有什麼不了解的地方，歡迎提出。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 105;
const int inf = 1000000000;
const int mod = 1000000007;
__int64 s[N];
bool v[N];
int w[N][N];
int dfs(int t,int x)
{
    if(t==1)
        return w[t][x];
    return dfs(t-1,w[t][x]);
}
int main()
{
    int n,m,i,j,k,x;
    bool flag;
    __int64 ans;
    s[0]=1;
    for(i=1;i<N;i++)
        s[i]=(s[i-1]*i)%mod;
    while(~scanf("%d%d",&n,&m))
    {
        flag=true;
        for(k=0,i=1;i<=m;i++)
        {
            scanf("%d",&x);
            if(x==-1)
                k++;
            else
            {
                memset(v,false,sizeof(v));
                v[x]=true;w[i][1]=x;
                for(j=2;j<=n;j++)
                {
                    scanf("%d",&x);
                    v[x]=true;
                    w[i][j]=x;
                }
                for(j=1;j<=n;j++)
                    if(!v[j])
                        break;
                if(j<=n)
                    flag=false;
            }
        }
        /*for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
                printf("%d ",w[i][j]);
            printf("\n");
        }*/
        if(!flag)
            puts("0");
        else if(!k)
        {
            for(i=1;i<=n;i++)
                if(dfs(m,i)!=i)
                    break;
            //printf("%d*\n",i);
            if(i>n)
                puts("1");
            else
                puts("0");
        }
        else
        {
            for(ans=1,i=1;i<k;i++)
                ans=ans*s[n]%mod;
            printf("%I64d\n",ans);
        }
    }
    return 0;
}
           

菜鳥成長記