本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-01 08:32:46

题意

你有无数包卡牌，每包有 $n$ 张，同时有 $n$ 种稀有卡牌，每张稀有卡牌在每包中出现的概率为 $p_i$，问期望拆多少包卡牌可以获得 $m$ 张稀有卡牌。

$n \le 5000$，$m \le 5000$。

思路

很显然，我们可以用 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

#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;
}