nowcoder multi addrace L

题目描述

有一个 multiset ，对 中的数做排列，得到序列集合 ，求
。其中 ，即自然数中没有在该序列中出现过的最小值。

解题思路

首先我们观察到，我们可以统计每一个 的贡献值。具体贡献如下：

对于每一个 ，它的结果都是 ，它的个数有 该序列之外的序列有 个。将 插入进去的方式有 种。总共的个数有

接下来考虑求解答案。要求解所有满足这个的答案，我们考虑生成函数的思想。首先经过观察我们可以先将 分离出来，我们单独求解

我们考虑直接枚举 ，计算答案。
当 时，对应的答案贡献为

我们记

那么所有 的答案贡献就为

我们发现这个 对于答案的统计很不方便，于是就看能否将 的贡献拆分成 份分别提交到前面的答案贡献中，以 为例子就是

这个式子看起来不好合并，于是我们给它添一项

那么答案就变成了

思考添加的这一项的组合含义，表示每一个 都大于 ，这样就有 项，这种情况的个数为 所以对答案无影响。

因此，总的答案就变为了

这个式子非常的恶心，我们考虑一个简单版本怎么求 ，直接分治处理然后用 合并即可。

那么我们看看这个式子是否具有局部性。令

于是我们可以每次计算的时候维护四个多项式的值，分别是 、 、 、 然后用 合并得到答案。