• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Dec 4th, 2012 70 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.
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.         }
174.         for (i=0; i<V-1; i++) {
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top