C. LRU 概率dp+状压dp
题目大意：
有一个缓存，它最多可以存k条记录，如果超过k条记录，那么最早存进去的记录会被删除，如果其中有一条记录之前已经存过，那么会更新这条记录的时间，并且将之前的那条记录删除。
第一行，给你n条记录和缓存的大小k，第二行，给你每条记录存进缓存的概率，问经过无穷次存储之后，最后每条记录存进缓存的概率。
题解：
这种概率题目我其实很不擅长，又涉及到无穷，更是一头雾水。。。
从后往前考虑！！！考虑最后是一个什么样的状态
考虑中间状态形成的原因以及概率的求法：
- 第一种：自增，假设原来缓存已经有1、2，那么又变成1、2这种状态是可以1这条记录或者2这条记录加进缓存，这个就是自增
- 第二种：其他状态转移过来，假设状态是1、2，那么是不是可以从两种状态转移过来，第一种就是缓存1这条记录，第二种就是缓存有2这条记录
考虑最后状态形成的原因以及概率的求法：
-
这个最后一个状态和中间状态肯定是不一样的，因为最后一个状态确定之后，这个缓存就不会改变了，因为都已经是最后的状态了，这个时候就只需要求最后状态的概率。
-
最后的这个状态是肯定不会是自增形成的，因为如果是自增，那么永远填不满这k个值，因为重复的元素要被删除。所以最后一个状态只能从其他状态转移过来。
知道这些之后就可以列式子了，
(dp[i]=sum(p[j])*dp[i]+sum(dp[i igotimes (1<<j)]*p[j]))
因为 (dp[i]) 表示 (i) 这种状态的出现的概率之和，所以 (dp[0]=1) 因为一开始的(dp[0]=1) 之后永远都不会出现缓存是0条记录的情况，所以可知 (dp[0]=1)
#include <bits/stdc++.h>
#define id first
#define val second
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn=25;
const double eps = 1e-8;
typedef long long ll;
double dp[1<<21],p[maxn],ans[maxn];
int main(){
int n,k,now=0;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) {
scanf("%lf",&p[i]);
if(p[i]>eps) now++;
}
dp[0]=1;
k=min(k,now);
for(int i=1;i<(1<<n);i++){
int x= i,num=0;
double sum=0,res=1.0;
for(int j=0;j<n;j++){
int tmp=x&(1<<j);
if(tmp) {
num++;
res-=p[j];
sum+=p[j]*dp[x^(1<<j)];
}
}
if(num==k) {
// printf("kk dp[%d]=%f sum=%f res=%f
",i,dp[i],sum,res);
dp[i]=sum;
for(int j=0;j<n;j++){
int tmp=x&(1<<j);
if(tmp) ans[j]+=dp[i];
}
}
if(num<k) dp[i]=sum/res;
// if(!((i&(1<<3))||(i&(1<<5))||(i&(1<<7))||(i&(1<<9))
// ||(i&(1<<11))||(i&(1<<13))||(i&(1<<15))||(i&(1<<16))||(i&(1<<17))||(i&(1<<18))||(i&(1<<19)))){
// printf("dp[%d]=%f sum=%f res=%f
",i,dp[i],sum,res);
//
// }
}
for(int i=0;i<n;i++) printf("%.10f ",ans[i]);
printf("
");
}