首页 > 代码库 > UVA 11174 Stand in a Line 树形dp+计数

UVA 11174 Stand in a Line 树形dp+计数

2024-08-09 10:46:18   218人阅读

题意：白书的P103.

加个虚根就可以了。。。然后就是一个多重集排列。

[java] view plaincopy技术分享技术分享
  1. import java.io.PrintWriter;  
  2. import java.util.ArrayList;  
  3. import java.util.Scanner;  
  4.   
  5. public class Main {  
  6.     static int N = 40100;  
  7.     ArrayList<Integer>[] G = new ArrayList[N];  
  8.     static long mod = 1000000007;  
  9.     long[] way = new long[N];  
  10.     long[] fac = new long[N];  
  11.     int n, m;  
  12.     int[] father = new int[N], siz = new int[N];  
  13.     long Pow(long x, long y){  
  14.         long ans = 1;  
  15.         while(y > 0){  
  16.             if(y%2 == 1L)  
  17.                 ans = (ans*x)%mod;  
  18.             x = (x*x)%mod;  
  19.             y >>= 1;  
  20.         }  
  21.         return ans;  
  22.     }  
  23.     void dfs(int u, int fa){  
  24.         siz[u] = 1; way[u] = 1L;  
  25.         for(int i = 0; i < G[u].size(); i++){  
  26.             int v = G[u].get(i); if(v == fa)continue;  
  27.             dfs(v, u);  
  28.             siz[u] += siz[v];  
  29.             way[u] = (way[u]*way[v])%mod;  
  30.         }  
  31.         way[u] = (way[u]* fac[siz[u]-1]) %mod;  
  32.         for(int i = 0; i < G[u].size(); i++){  
  33.             int v = G[u].get(i); if(v == fa)continue;  
  34.             way[u] = (way[u] * Pow(fac[siz[v]], mod-2))%mod;  
  35.         }  
  36.     }  
  37.     void init(){  
  38.         n = cin.nextInt();  m = cin.nextInt();  
  39.         for(int i = 0; i <= n; i++){  
  40.             father[i] = 0;  
  41.             G[i].clear();  
  42.         }  
  43.         while(m-- > 0){  
  44.             int u = cin.nextInt(), v = cin.nextInt();  
  45.             G[v].add(u);  
  46.             father[u] = v;  
  47.         }  
  48.         for(int i = 1; i <= n; i++)  
  49.             if(father[i] == 0){  
  50.                 G[0].add(i);  
  51.             }  
  52.     }  
  53.     void work() {         
  54.         for(int i = 0; i < N; i++)G[i] = new ArrayList();  
  55.         fac[0] = 1L;  
  56.         for(int i = 1; i < N; i++)   fac[i] = fac[i-1]*i%mod;  
  57.         int T = cin.nextInt();  
  58.         while(T-->0){  
  59.             init();  
  60.             dfs(0,0);  
  61.             out.println(way[0]);  
  62.         }  
  63.     }  
  64.   
  65.     Main() {  
  66.         cin = new Scanner(System.in);  
  67.         out = new PrintWriter(System.out);  
  68.     }  
  69.   
  70.     public static void main(String[] args) {  
  71.         Main e = new Main();  
  72.         e.work();  
  73.         out.close();  
  74.     }  
  75.   
  76.     public Scanner cin;  
  77.     public static PrintWriter out;  
  78. } 

UVA 11174 Stand in a Line 树形dp+计数


联系
我们