http://acm.pku.edu.cn/JudgeOnline/problem?id=3744
从题意可以得出递推式: P
N = p * P
N - 1 + (1 - p) * P
N - 2;
可导出通项公式: P
N = P
start / (p - 2) * ((p - 1)
N + 1 - 1)
之后就可以直接套用公式了.
/**
* @version 2009/08/28
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
public static void main(String[] argv) throws Exception {
int[] list = new int[10];
int i, temp, last;
int N;
double p, val;
boolean found;
while (true) {
N = nextInt();
p = nextDouble();
for (i = 0; i < N; i++) list[i] = nextInt();
Arrays.sort(list, 0, N);
for (temp = N, N = i = 1; i < temp; i++)
if (list[i] != list[i - 1]) list[N++] = list[i];
for (found = false, i = 0; !found && i < N; i++)
if (list[i] == 1 || i > 0 && list[i] == list[i - 1] + 1)
found = true;
if (found) {
System.out.println("0.0000000");
continue;
}
last = 1;
val = 1.0;
for (i = 0; i < N; i++) {
val = val * (Math.pow(p - 1, list[i] - last) - 1.0) / (p - 2.0) * (1 - p);
last = list[i] + 1;
}
System.out.format("%.7f%n", val);
}
}
private static int nextInt() throws Exception {
return Integer.parseInt(next());
}
private static double nextDouble() throws Exception {
return Double.parseDouble(next());
}
private static String next() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return st.nextToken();
}
}