ABC382-E 题解
刘梓轩2010
·
·
题解
题意
你有无数包卡牌，每包有 n 张，同时有 n 种稀有卡牌，每张稀有卡牌在每包中出现的概率为 p_i，问期望拆多少包卡牌可以获得 m 张稀有卡牌。
## 思路
很显然，我们可以用 dp 解决这个问题。
设 $f_i$ 为**至少**获得 $i$ 张稀有卡牌的期望拆的包数，$g_i$ 为每包**恰好**获得 $i$ 张卡牌的概率。
我们首先求解 $g$，我们可以考虑新加进来一种稀有卡牌，设新加进来第 $i$ 种稀有卡，考虑转移 $g_j$，那么有两种情况，一种是前 $i-1$ 种卡牌已经拆出 $j$ 张的概率，另一种是前 $i-1$ 种卡牌拆出 $j-1$ 张，同时拆出来了第 $i$ 种的概率，于是转移方程为 $g_j=g_j\times (1-p_i)+g_{j-1}\times p_i$。类似于背包，要倒序转移。
再来求解 $f$。转移时，我们可以枚举这一次拆出来的数量，借助 $g$ 转移。要让总卡牌数至少为 $i$，如果这一包拆出 $j$ 张，则原来至少有 $\max\{0,i-j\}$ 张。方程即为 $f_i=1+\sum_{j=0}^n f_{\max\{0,i-j\}}\times g_j$。
这样还有个问题，$f_i$ 会从自己转移过来，只需要把右边带 $f_i$ 的项移到右边即可。
最终的式子即为 $f_i=\tfrac{1}{1-g_0}\times(1+\sum_{j=1}^n f_{\max\{0,i-j\}}\times g_j)$。
不理解可以结合代码食用。
## Code
```c++
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=5000+10;
const int inf=0x3f3f3f3f3f3f3f3f;
double g[N];
double f[N];
int n,x;
double p[N],ans;
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>p[i];
p[i]/=100;
}
g[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=n;j>=1;j--)
{
g[j]=g[j]*(1-p[i])+g[j-1]*p[i];
}
g[0]*=(1-p[i]);
}
for(int i=1;i<=x;i++)
{
f[i]=1;
for(int j=1;j<=n;j++)
{
f[i]+=f[max(0ll,i-j)]*g[j];
}
f[i]/=(1-g[0]);
}
printf("%.8lf",f[x]);
return 0;
}
```