fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. import static java.lang.Math.*;
  6. import static java.lang.Character.*;
  7. import static java.util.Arrays.*;
  8. import static java.util.Collections.*;
  9. import static java.math.BigInteger.*;
  10.  
  11. class D {
  12. 	static final char PROB = D.class.getSimpleName().charAt(0);
  13. 	static final boolean PRAC = false;
  14.  
  15. 	static final int INF = 1 << 20;
  16. 	static final int[] di = { -1, 0, 0, 1 };
  17. 	static final int[] dj = { 0, -1, 1, 0 };
  18. 	static Scanner sc = new Scanner(System.in);
  19.  
  20. 	static final int MAX = 1000;
  21. 	static final double[] g = new double[MAX + 1];
  22. 	static final double[][] cef = new double[MAX + 1][MAX + 1];
  23. 	final int N;
  24. 	final int[] a;
  25.  
  26. 	public D() {
  27. 		N = sc.nextInt();
  28. 		a = new int[N];
  29. 		for(int i =0 ; i < N; i++)
  30. 			a[i] = sc.nextInt() - 1;
  31. 	}
  32.  
  33. 	public String solve() {
  34. 		UnionFind uf = new UnionFind(N);
  35. 		for(int i = 0; i < N; i++)
  36. 			uf.union(i, a[i]);
  37. 		double ans = 0;
  38. 		for(int i : uf.t)
  39. 			if(i < 0)
  40. 				ans += f(-i);
  41. 		return "" + ans;
  42. 	}
  43.  
  44. 	static double f(int i) {
  45. 		return i == 1 ? 0. : g[i] + 1.;
  46. 	}
  47.  
  48. 	static double g(int i) {
  49. 		double ret = 1.;
  50. 		for(int j = 1; j < i; j++)
  51. 			ret += cef[i][j] * (g[j] + f(i - j));
  52. 		ret /= 1. - cef[i][0];
  53. 		ret -= 1.;
  54. 		return ret;
  55. 	}
  56.  
  57. 	static double cef(int n, int k) {
  58. 		double ret = 1.;
  59. 		for(int i = 1; i <= k; i++) {
  60. 			ret *= n - i;
  61. 			ret /= i;
  62. 		}
  63. 		for(int i = 1; i < n; i++)
  64. 			ret /= 2.;
  65. 		return ret;
  66. 	}
  67.  
  68. 	static {
  69. 		for(int n = 1; n <= MAX; n++)
  70. 			for(int k = 0; k < n; k++)
  71. 				cef[n][k] = cef(n, k);
  72. 		for(int i = 2; i <= MAX; i++)
  73. 			g[i] = g(i);
  74. 	}
  75.  
  76. 	class UnionFind {
  77. 		final int[] t;
  78. 		public UnionFind(int size) {
  79. 			t = new int[size];
  80. 			fill(t, -1);
  81. 		}
  82. 		void union(int x, int y) {
  83. 			x = root(x);
  84. 			y = root(y);
  85. 			if(x == y)
  86. 				return;
  87. 			t[x] += t[y];
  88. 			t[y] = x;
  89. 		}
  90. 		int root(int x) {
  91. 			return t[x] < 0 ? x : (t[x] = root(t[x]));
  92. 		}
  93. 	}
  94.  
  95. 	public static void main(String... args) {
  96. 		// large();
  97. 		int T = Integer.parseInt(sc.nextLine());
  98. 		for (int t = 1; t <= T; t++) {
  99. 			System.err.printf("Case #%s%n", t);
  100. 			System.out.printf("Case #%s: %s%n", t, new D().solve());
  101. 		}
  102. 		System.err.println("done.");
  103. 	}
  104.  
  105. 	public static void small() {
  106. 		String in = PROB + "-small" + (PRAC ? "-practice" : "-attempt" + 0) + ".in";
  107. 		String out = PROB + "-small.out";
  108. 		try {
  109. 			if (!PRAC)
  110. 				for (int i = 1; new File(PROB + "-small" + "-attempt" + i + ".in").exists(); i++)
  111. 					in = PROB + "-small" + "-attempt" + i + ".in";
  112. 			System.setIn(new BufferedInputStream(new FileInputStream(in)));
  113. 			System.setOut(new PrintStream(out));
  114. 		} catch (Exception e) {
  115. 			e.printStackTrace();
  116. 			System.exit(0);
  117. 		}
  118. 		sc = new Scanner(System.in);
  119. 	}
  120.  
  121. 	public static void large() {
  122. 		String in = PROB + "-large" + (PRAC ? "-practice" : "") + ".in";
  123. 		String out = PROB + "-large.out";
  124. 		try {
  125. 			System.setIn(new BufferedInputStream(new FileInputStream(in)));
  126. 			System.setOut(new PrintStream(out));
  127. 		} catch (Exception e) {
  128. 			e.printStackTrace();
  129. 			System.exit(0);
  130. 		}
  131. 		sc = new Scanner(System.in);
  132. 	}
  133.  
  134. 	private static void debug(Object... os) {
  135. 		System.err.println(deepToString(os));
  136. 	}
  137. }
  138.  
Success #stdin #stdout 5.13s 213440KB
comments (?)
stdin
copy 
3
2
2 1
3
1 3 2
4
2 1 4 3
stdout
copy 
Case #1: 2.0
Case #2: 2.0
Case #3: 4.0
https://ideone.com/TZxsR
language:
Java (HotSpot 12)
created:
13 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!