问一个n长度的数有多少种可以利用某些转换转换成只有1到N的数。可以把能用A换B的变成从A连向B的一条边
由于题目说明每个点的出度和入度不大于1。因此图中只有两种情况，一个是链，一个是环。链的话，如果长度是M，就表示从长度为k的未放置格中取出m个位置来放置这m个数。而因此链上的点可以向下转换，因此可以用DP来解决dp[i,j]表示第i个点占用了j个位置的方案数dp[i,j]=sum(dp[i-1][k]*c[j][k])。环也一样，不过链要求I各点最多只能放I个位置，不然链头的某些点就不能从某些点得到了。环就无此限制
最后扫描一下图，统计一下就行了
1 #include<stdio.h>
2 #include<iostream>
3 #include<string>
4 #include<vector>
5 #include<map>
6 #include<queue>
7 #include<algorithm>
8 #define M 1000
9 #define clr(x) memset(x,0,sizeof(x))
10 #define _clr(x) memset(x,-1,sizeof(x))
11 #define fr(i,a,b) for(int i=a;i<b;++i)
12 #define pf printf
13 #define sf scanf
14 #define pb push_back
15 #define mp make_pair
16 #define ll long long
17 #define debug 1
18 using namespace std;
19 const ll mod=(ll)1000000007;
20 ll dp1[201][201],dp2[201];
21 ll c[201][201];
22 ll pow(int a,int b)
23 {
24 ll ret=1;
25 while(b>0)
26 {
27 if(b&1){ret=(ret*a)%mod;}
28 a=((ll)a*a)%mod;
29 b>>=1;
30 }
31 return ret;
32 }
33 void init()
34 {
35 clr(c);
36 c[0][0]=1;
37 fr(i,1,201)
38 {
39 c[i][0]=1;
40 fr(j,1,i+1)
41 {
42 c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
43 }
44 }
45 clr(dp1);
46 dp1[0][0]=1;
47 //链DP
48 fr(i,1,201)
49 {
50
51 fr(j,0,i+1)
52 {
53 //链上第i个节点用了j个位置
54 fr(k,0,j+1)
55 dp1[i][j]=(dp1[i][j]+dp1[i-1][k]*c[j][j-k])%mod;
56 }
57 }
58 //环
59 fr(i,1,201)
60 {
61 dp2[i]=pow(i,i);
62 }
63 }
64 int to[201];
65 int v[201];
66 int s[201];
67 vector<int>h,l;
68 vector< pair<int,int> >ft;
69 int main()
70 {
71 freopen("in.txt","r",stdin);
72 init();
73 int T;
74 sf("%d",&T);
75 while(T--)
76 {
77 int n,m;
78 sf("%d%d",&n,&m);
79 _clr(to);
80 clr(v);
81 _clr(s);
82 fr(i,0,m)
83 {
84 int a,b;
85 sf("%d%d",&a,&b);
86 to[a]=b;
87 s[b]=a;
88 }
89 int pos=n;
90 ll ans=1;
91 fr(i,0,n)
92 {
93 if(v[i])continue;
94 int now=i;
95 int count=0;
96 while(now!=-1&&!v[now])
97 {
98 v[now]=1;
99 ++count;
100 //if(to[now]==-1)break;
101 now=to[now];
102 }
103 if(now!=-1)
104 {
105 // pf("cc=%d\n",count);
106 ans=(ans*c[pos][count])%mod;
107 ans=(ans*dp2[count])%mod;
108 pos-=count;
109 }
110 else
111 {
112 now=s[i];
113 while(now!=-1)
114 {
115 //pf("now=%d\n",now);
116 v[now]=1;
117 now=s[now];
118 ++count;
119 }
120 //pf("c=%d\n",count);
121 ans=(ans*c[pos][count])%mod;
122 ans=(ans*dp1[count][count])%mod;
123 pos-=count;
124 }
125 }
126 pf("%lld\n",ans);
127 }
128 return 0;
129 }
130