CF1740F Conditional Mix 笔记

找性质再计数的题目。

题意可以简化成，有 $n$ 个盒子，往每个盒子里放球，其中盒子内不能有同色球，要求「盒子内球数」$M_{1\dots n}$ 的组合的个数。

由于是组合，因此我们钦定一种顺序，令 $M_i\ge M_{i+1}$ 进行计数。

感性理解一下这个过程，相当于对于同一种颜色的 $k$ 个球，我们把它放进 $k$ 个不同的盒子里，那么按照钦定的顺序，我们把所有球尽量往前放，可以得到在这种情况下，第 $i$ 个盒子最多能放的球数 $\underset{i}{lim}$。

此时第 $i$ 个盒子存在一些球第 $i+1$ 个盒子中没有，我们把这些球从第 $i$ 个盒子中拿出来放进第 $i+1$ 个盒子就可以构成一种新的组合，因此得出结论，合法的 $M$ 满足：

$$\mathrm{\forall }i,\sum _{j\le i}{\lim }_j\ge \sum _{j\le i}{M}_j\wedge M_i\ge M_{i+1}$$

得到这个条件我们就可以 DP 了，设 $f_{i,j,k}$ 表示考虑 $M_{1\dots i}$，$j=\sum _{j^{\prime }\le i}{M}_{j^{\prime }}$，$M_i=k$ 的方案数，转移

$$f_{i,j,k}\leftarrow \sum _{l\ge k}{f}_{i-1,j-k,l}$$

$\sum$ 用后缀和优化，可以发现根据定义，$k\le \lfloor n÷i\rfloor$，因此总状态数是 $O(n^2\ln n)$，转移 $O(1)$，时间复杂度 $O(n^2\ln n)$，空间复杂度可以把第一维滚掉变成 $O(n^2)$。