題目鏈接:點擊打開鏈接
題意:白書的P103.
加個虛根就可以了。。。然後就是一個多重集排列。
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Scanner; public class Main { static int N = 40100; ArrayList[] G = new ArrayList[N]; static long mod = 1000000007; long[] way = new long[N]; long[] fac = new long[N]; int n, m; int[] father = new int[N], siz = new int[N]; long Pow(long x, long y){ long ans = 1; while(y > 0){ if(y%2 == 1L) ans = (ans*x)%mod; x = (x*x)%mod; y >>= 1; } return ans; } void dfs(int u, int fa){ siz[u] = 1; way[u] = 1L; for(int i = 0; i < G[u].size(); i++){ int v = G[u].get(i); if(v == fa)continue; dfs(v, u); siz[u] += siz[v]; way[u] = (way[u]*way[v])%mod; } way[u] = (way[u]* fac[siz[u]-1]) %mod; for(int i = 0; i < G[u].size(); i++){ int v = G[u].get(i); if(v == fa)continue; way[u] = (way[u] * Pow(fac[siz[v]], mod-2))%mod; } } void init(){ n = cin.nextInt(); m = cin.nextInt(); for(int i = 0; i <= n; i++){ father[i] = 0; G[i].clear(); } while(m-- > 0){ int u = cin.nextInt(), v = cin.nextInt(); G[v].add(u); father[u] = v; } for(int i = 1; i <= n; i++) if(father[i] == 0){ G[0].add(i); } } void work() { for(int i = 0; i < N; i++)G[i] = new ArrayList(); fac[0] = 1L; for(int i = 1; i < N; i++) fac[i] = fac[i-1]*i%mod; int T = cin.nextInt(); while(T-->0){ init(); dfs(0,0); out.println(way[0]); } } Main() { cin = new Scanner(System.in); out = new PrintWriter(System.out); } public static void main(String[] args) { Main e = new Main(); e.work(); out.close(); } public Scanner cin; public static PrintWriter out; }