题目描述
有 $n$ 个无区别的锁， $N$ 把无区别的钥匙都被藏， $M$ 个藏钥匙的地方，每个藏钥匙的地方最多藏 $a_i$ 个钥匙，并且这个地方被发现的概率为 $p_i$ ，求所有藏钥匙的方案能够找到至少 $n$ 个的概率之和。
数据范围
所有测试数据满足 $1 leq M leq 100,1 leq n leq N leq sum a_{i}, 1 leq N, a_{i} leq 10^{9}, 1 leq d leq 10^{7}, 0 leq p_{i}<998244353,N leq 100 d, d |left(a_{i}+1 ight)$ ，但并不保证 $d | N$ 或 $d | n$ 。
题解
orzsz
有个关键信息是 $d |left(a_{i}+1 ight)$ 和 $N leq 100 d$ ，所以我们可以先对每个藏钥匙的地方分配 $d$ 倍的钥匙数量，然后每个位置最终只能再放 $[0,d)$ 把钥匙。然后我们考虑如果我们知道了每个位置第一步分配的情况，那后面再分配的话我们需要知道被发现的位置一开始分配了多少，这样才能够去保证这些被发现的位置钥匙之和至少为 $n$ 。
所以我们考虑 $ ext{dp}$ ： $f[x][i][j][k]$ 表示前 $x$ 个地方，有 $k$ 个位置最后会被发现，这 $k$ 个位置总共分配了 $j imes d$ 把钥匙，这 $x$ 个位置总共分配了 $i imes d$ 把钥匙。转移显然。
然后假设第一步分配后还有 $x$ 把钥匙没有被分配，被发现的 $k$ 个位置中还差 $y$ 把钥匙达到 $n$ 。我们可以把这 $k$ 个位置放在前面，考虑先分配 $y$ 把钥匙在这 $k$ 个位置上。由于 $M$ 很小，且钥匙无序，所以可以枚举 $u$ 表示第 $y$ 把钥匙放在 $u$ 上，且 $y-1$ 把钥匙放在了 $u$ 及之前， $x-y$ 把钥匙放在 $u$ 及之后的位置，如果我们不考虑分配不小于 $d$ ，那就可以隔板法。不小于 $d$ 的话考虑容斥，可以考虑在原本 $ ext{dp}$ 的时候就进行容斥，即转移的时候考虑这个位置之后分配会不小于 $d$ 的话，那就强制这个位置多选一个 $d$ 容斥转移即可。这样后面再分配直接隔板就可以了。
效率： $O(m^2 imes (frac{N}{d})^2)$ 。