Advertisement
Guest User

Untitled

a guest
Dec 4th, 2012
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.48 KB | None | 0 0
  1. public class InducedSubgraphs{
  2.    
  3.     long    MOD = 1000000009l;
  4.     int     INF = (1<<29);
  5.     int     V;       //number of vertices
  6.     long    C[][];   // C[n][k] = Binomial
  7.     long    fact[];  // fact[n] = n! (factorial)
  8.  
  9.     boolean adj[][];  //adjacency matrix
  10.    
  11.    
  12.     int     cnt[][];    //cnt[p][x] total size of the subgraph with x as root
  13.                         // and p is the parent of node x.
  14.     long    perm[][];   //perm[p][x] is the number of ways to assign labels
  15.                         //to the children of x when p is its parent.
  16.                        
  17.                          
  18.     long    dp[][][][]; //dp[p][x][s][t]:
  19.                         // The number of ways to assign s small labels
  20.                         // and t big labels to the subtree rooted at x, when
  21.                         // p is the parent of x.
  22.  
  23.    
  24.     // The number of ways to assign labels to the subgraph that has x as root
  25.     // (when p is the parent).
  26.     //
  27.     public void dfs_easy(int p, int x){
  28.         int i;
  29.        
  30.         if (cnt[p][x] != 0) {
  31.             return;
  32.         }
  33.        
  34.         perm[p][x] = 1;
  35.  
  36.         int sum = 0; //number of children in the subtree
  37.         for(i=0; i<V; i++) if(adj[x][i] && p != i) {
  38.             dfs_easy(x, i);
  39.             long s = C[ sum + cnt[x][i] ][sum];
  40.             long t = perm[x][i];
  41.             perm[p][x] = perm[p][x] * s % MOD * t % MOD;
  42.             sum += cnt[x][i];
  43.         }
  44.         cnt[p][x] = sum + 1;
  45.     }
  46.    
  47.     public int solve_easy(int K) {
  48.         // For 2K <= V:
  49.         int i,j,k;
  50.         int dist[][] = new int[V][V];
  51.         // Floyd-Warshall algorithm to quickly find the distances between
  52.         // each pair of nodes.
  53.         for(i=0; i<V; i++) for(j=0; j<V; j++) {
  54.             if (i!=j) {
  55.                 dist[i][j] = (adj[i][j] ? 1 : INF);
  56.             }
  57.         }
  58.         for(k=0; k<V; k++) {
  59.             for(i=0; i<V; i++) for(j=0; j<V; j++) {
  60.                 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
  61.             }
  62.         }
  63.        
  64.         int d = V - 2*K + 1;
  65.         // In this case, there has to be a chain of nodes of size d+1 in the middle section
  66.         // each end of this end is connected with the small and big sections.
  67.         int u, v, u2, v2;
  68.         long ans = 0;
  69.        
  70.         for(u=0;u<V;u++) for(v=0;v<V;v++) if (u!=v) {
  71.             if(dist[u][v] == d) {
  72.                 u2 = v2 = 0;
  73.                 // Seek u2 and v2, the appropriate parents for the
  74.                 // subtrees at u and v, respectively
  75.                 while ( ! adj[u][u2] || dist[u2][v] >= dist[u][v] ) {
  76.                     u2++;
  77.                 }
  78.                 while ( ! adj[v][v2] || dist[u][v2] >= dist[u][v] ) {
  79.                     v2++;
  80.                 }
  81.                 // Do the subtrees at u and v have the exact required sizes?
  82.                 if (cnt[u2][u] == K && cnt[v2][v] == K) {
  83.                     ans = (ans + perm[u2][u] * perm[v2][v]) % MOD;
  84.                 }
  85.             }
  86.         }
  87.        
  88.         return (int)ans;
  89.     }
  90.    
  91.     public long[][] merge( long[][] a, long[][] b ){
  92.         int i,j,k,l;
  93.         int A = a.length - 1, B = b.length - 1;
  94.        
  95.         // a[x][y] : The current number of ways to have
  96.         //           x "small" children and y "big" children in total.
  97.         // b[x][y] : The number of ways to have
  98.         //           x "small" children and y "big" children in total.
  99.         //           in the node that we need to combine with the result in a[][]
  100.  
  101.         // c[x][y] : The result after combining.
  102.         long c[][] = new long[A+B+1][A+B+1];
  103.        
  104.         for(i=0;i<=A;i++) for(j=0;j<=A;j++) for(k=0;k<=B;k++) for(l=0;l<=B;l++) {
  105.             long p = a[i][j] * b[k][l];
  106.             long q = C[i+k][k];
  107.             long r = C[j+l][l];
  108.             long tmp = p % MOD * q % MOD * r % MOD;
  109.             c[i+k][j+l] = (c[i+k][j+l] + tmp) % MOD;
  110.         }
  111.        
  112.         return c;
  113.     }
  114.    
  115.     public void dfs(int p, int x){
  116.         int i;
  117.        
  118.         if (dp[p][x].length == 0) {
  119.            
  120.             long a[][] = new long[2][2];
  121.             a[0][0] = 1;
  122.            
  123.             for(i=0;i<V;i++) if(adj[x][i] && p != i) {
  124.                 dfs(x, i);
  125.                 a = merge(a, dp[x][i]);
  126.             }
  127.            
  128.             // If we decide the current node to be small, the whole
  129.             // subtree must be small:
  130.             a[cnt[p][x]][0] = perm[p][x]; //There are perm[p][x] ways to label
  131.             // If we decide the current node to be big, the whole
  132.             // subtree must be big:
  133.             a[0][cnt[p][x]] = perm[p][x];
  134.            
  135.             dp[p][x] = a;
  136.         }
  137.     }
  138.    
  139.     public int solve(int K){
  140.         int i,j;
  141.        
  142.         dp = new long[V+1][V+1][0][0];
  143.         for(i=0;i<V;i++) dfs(V, i);
  144.        
  145.         long ans = 0;
  146.         int center = 2*K - V;
  147.         for (i=0; i<V; i++) {
  148.             // number of ways in which node i is a center node:
  149.             ans = (ans + dp[V][i][V-K][V-K]) % MOD;
  150.         }
  151.         // - Each result is repeated {center} times.
  152.         // - we also need to choose labels for the center nodes.
  153.         // -> Multiply by center! / center = (center-1)!
  154.        
  155.         ans = ans * fact[center - 1] % MOD;
  156.         return (int)ans;
  157.     }
  158.    
  159.     public int getCount(int[] edge1, int[] edge2, int K){
  160.         int i,j;
  161.        
  162.         V = edge1.length + 1;
  163.        
  164.         // Calculate the factorial
  165.         fact = new long[V + 1];
  166.         fact[0] = 1;
  167.         for( i=1; i<=V; i++) {
  168.             fact[i] = i * fact[i-1] % MOD;
  169.         }
  170.         if (K == 1) { // a simple corner case, any permutation of labels will work
  171.             return (int)fact[V];
  172.         }
  173.         adj = new boolean[V][V];
  174.         for (i=0; i<V-1; i++) {
  175.             adj[edge1[i]][edge2[i]] = adj[edge2[i]][edge1[i]] = true;
  176.         }
  177.        
  178.         // Pascal's triangle
  179.         C = new long[V+1][V+1];
  180.         for(i=0;i<=V;i++) {
  181.             C[i][0] = 1;
  182.             for(j=1; j<=i; j++) {
  183.                 C[i][j] = ( C[i-1][j] + C[i-1][j-1] ) % MOD;
  184.             }
  185.         }
  186.         // In both cases, we need to calculate the cnt[][] and perm[][] tables:
  187.         cnt = new int[V+1][V+1];
  188.         perm = new long[V+1][V+1];
  189.         for(i=0;i<V;i++) {
  190.             dfs_easy(V, i);
  191.         }
  192.         if (V >= 2*K) {
  193.             return solve_easy(K);
  194.         } else {
  195.             return solve(K);
  196.         }
  197.     }
  198.  
  199. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement