fork(2) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. static double p[][];
  11. 	static double dp[];
  12. 	static int n;
  13.  
  14. 	public static int BitCount(int u) {
  15. 		int uCount;
  16.  
  17. 		uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
  18. 		return ((uCount + (uCount >> 3)) & 030707070707) % 63;
  19. 	}
  20.  
  21. 	public static double f(int mask) {
  22. 		if (dp[mask] > -0.5)
  23. 			return dp[mask];
  24.  
  25. 		dp[mask] = 0;
  26.  
  27. 		int ones = BitCount(mask);
  28. 		double pairs = (((ones * (ones + 1))) >> 1);
  29. 		//System.out.println(pairs);
  30.  
  31. 		for (int i = 0; i < n; i++) {
  32. 			for (int j = 0; j < n; j++) {
  33. 				if ((mask & (1 << i)) != 0 && (mask & (1 << j)) == 0)
  34. 					dp[mask] += f(mask | (1 << j)) * p[i][j] / pairs;
  35. 			}
  36. 		}
  37.  
  38. 		return dp[mask];
  39. 	}
  40.  
  41. 	public static void main(String[] args) throws NumberFormatException,
  42. 			IOException {
  43. 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  44. 		n = Integer.parseInt(bf.readLine());
  45. 		p = new double[n][n];
  46. 		for (int i = 0; i < n; i++) {
  47. 			StringTokenizer st = new StringTokenizer(bf.readLine());
  48. 			for (int j = 0; j < n; j++) {
  49. 				p[i][j] = Double.parseDouble(st.nextToken());
  50. 			}
  51. 		}
  52.  
  53. 		dp = new double[1 << n];
  54.  
  55. 		Arrays.fill(dp, -1.0);
  56.  
  57. 		dp[(1 << n) - 1] = 1.;
  58.  
  59. 		for (int i = 0; i < n - 1; i++) {
  60. 			System.out.print(f(1 << i) + " ");
  61. 		}
  62.  
  63. 		System.out.println(f((1 << (n - 1))));
  64.  
  65. 	}
  66. }
Success #stdin #stdout 0.11s 320256KB
comments (?)
stdin
copy 
5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0
stdout
copy 
1.0 0.0 0.0 0.0 0.0
https://ideone.com/bxG58H
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!