闲扯

暴力场 $+\ FST$ 场。

题面

结论题，可以证明答案一定在最大的 $\log_2 x+2$ 个之间取到，然后直接暴力即可。

证明参考 $JKLover$ 的博客。

我们考虑当代价为 $\prod_{i=1}^N\binom{x_i}{k_i}$ 时，问题如何求解。（此时 $k_i$ 确定）

首先，当 $k_i=0$ 时，就是求划分的方案数，直接用隔板法即可解决。

考虑这个式子的组合意义， $\binom{x_i}{k_i}$ 就是在这 $x_i$ 个数中无序的选择 $k_i$ 个作为代表。

我们将这 $\sum k_i$ 个代表也抽出来作为隔板，那么我们就有 $N-1+\sum k_i$ 个隔板，有 $M-\sum k_i$ 个元素。

我们需要将这些元素分成 $N+\sum k_i$ 份，每份的大小都非负。

根据隔板法，我们可以知道方案数为 $\binom{N+M-1}{N+\sum k_i-1}$ 。可以发现，这个值只与 $\sum k_i$ 有关。

回到原问题，我们要求的是 $\prod_{i=1}^N x_i^{k_i}$ 。

我们将幂次转化为下降幂，有：

$\prod_{i=1}^N \sum_{j=0}^{k_i}S_{k_i}^j x_i^{\underline{j}}\\ =\prod_{i=1}^N \sum_{j=0}^{k_i}S_{k_i}^j\cdot j!\cdot \binom{x_i}{j}$

其中 $S$ 为第二类斯特林数。

这个东西我们用分治 $NTT$ 计算即可。

最大费用最大流。

每一个 $s$ 向 $T$ 连边，流量为 $1$ ，费用为 $0$ 。每一个 $t$ 向 $S$ 连边，流量为 $1$ ，费用为 $val$ 。

然后用差分的方法，每个点 $u$ 向 $fa_u$ 依次连流量为 $1$ ，费用为 $-F(i)+F(i-1)$ 的边，表示多覆盖一次减少的收益。

然后 $t$ 向 $s$ 连一条流量为 $1$ ，费用为 $-val$ 的边，表示不选这条链。

然后直接跑最大费用最大流即可。

但是这样可能会出现从中间跑掉的情况。事实上，这是不影响的。因为网络流要求流量平衡，所以最后一定会达到平衡状态，即每个从 $S$ 出来的点都会唯一对应一条流进 $T$ 的路径。