这又是什么毒瘤.....
解：把操作序列倒着来，就是考虑前k个入队的元素了。显然这样每个元素的概率不变。
状压。设fs表示当前元素为s的概率。
每次转移的时候选择一个不在s中的元素，作为下一个加入的元素。注意实际上有可能选择到在s中的元素。
然后我们设选择到s中元素的概率为x。
我们可能第一次就选到i，也有可能第2次选到，第3次选到......
概率分别是pi，x * pi，x2 * pi，......
无限求和有pi / (1 - x)。
所以最后转移的时候就是fs * pi * / (1 - x)
记得判断有用元素不足k的时候直接输出。
#include <bits/stdc++.h> const int N = , M = ; double p[N], f[M], ans[N], P[M];
int n, k, wp[M], cnt[M]; inline void out(int x) {
for(int i = n - ; i >= ; i--) printf("%d", (x >> i) & );
puts("");
return;
} int main() {
int Cnt = ;
scanf("%d%d", &n, &k);
for(int i = ; i < n; i++) {
scanf("%lf", &p[i]);
if(p[i] > ) Cnt++;
}
if(Cnt < k) {
for(int i = ; i < n; i++) {
if(p[i] > ) printf("1 ");
else printf("0 ");
}
return ;
} int lm = ( << n);
for(int i = ; i < n; i++) wp[ << i] = i;
for(int i = ; i < lm; i++) {
cnt[i] = + cnt[i - (i & (-i))];
P[i] = P[i - (i & (-i))] + p[wp[i & (-i)]];
}
f[] = ;
for(int i = ; i < lm; i++) {
//out(i);
if(cnt[i] == k) {
for(int s = ; s < n; s++) {
if(i & ( << s)) {
ans[s] += f[i];
}
}
continue;
}
if(cnt[i] > k) continue;
for(int s = ; s < n; s++) {
if((i >> s) & ) continue;
f[i | ( << s)] += f[i] * p[s] / ( - P[i]);
}
} for(int i = ; i < n; i++) printf("%.8f ", ans[i]);
return ;
}
AC代码