Guest User

Untitled

a guest
Dec 4th, 2012
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×