题解 CF2165B Marble Council

· · 题解

题解 CF2165B Marble Council

其他题

题意

给定一个可重集 a，求将 a 划分成若干个可重集后，在划分出的可重集中各取一个众数可能形成的新可重集的数量，对 998244353 取模。

数据范围：多测，\sum n\le 5000，值域 [1,n]。

做法

考虑对每个数拆贡献。然后当你试图考虑贡献怎么算的的时候你会发现：其实这个数只要出现在最终的集合中至少 1 次那么它必然对所有情况都贡献。因为拆多少个集合是随便的，而这个数拆出来的集合只出现它自己就行好。

所以现在只有在最终所得集合中不出现的数需要算算。

然后我们发现一个数字如果出现那每个该数字可以为每个不出现的数值（多个数值显然可以都是众数）提供一个位置。（这边区分一下，相等的多个数算一个数值多个数字，要不然不好表述）

这个条件转化一下，就是出现的数字总个数不小于数字个数最多的数值的数字个数就行。乍一看有点离谱，但其实你分最大的选不选讨论一下就会发现很合理。

然后直接暴力 dp：设 dp_{i,j} 表示前 i 个数值选了 j 个数字的方案数，转移时枚举 j 和当前数值选与不选，最终 j\ge\max cnt_i 的部分贡献答案。复杂度 O(n^2)。

启示：做不出来的时候看看条件能不能转化，尤其是本题根据七字真言已经确定了是 DP 然后你还设不出状态。类似的教训：