题解 CF1528F AmShZ Farm

· · 题解

牛逼题，看了题解才会做。

一个很明显的贪心是，逐个考虑 a 中的每个数，如果当前的数和之前的数重复了就把当前的数加 1，直到不重复为止。这样如果最后不存在 n+1 则说明可以把 a 转化为排列。

现在进行一个等价的描述：把 a 的值域拓展到 [1,n+1]，并且如果当前的数为 n+1，加 1 改为变成 1（就是在一个环上做）。可以把 a 转为排列的条件仍然是最后不存在 n+1。

这样对于一个可以被转化被排列的 a，将每个数在环上加 k\in[1,n]，最终的不存在的数就是 k。也就是说，一个可以被转化被排列的 a 对应 n 个不可以被转化被排列的 a'。

若这 $n+1$ 个序列称为一组，显然每一组中每个 $a$ 贡献相同。这意味着，对所有的 $a$ 进行计算后除掉 $n+1$ 即为答案。 现在考虑每个元素的贡献（显然是相同的），答案为这个乘上 $n+1$，然后最后又要除掉 $n+1$，消掉了。 枚举该元素出现次数，那么答案为 $$\sum_{i=0}^n C(n,i)i^kn^{n-i}$$ $n\le k$ 平凡，考虑 $n>k$ 的情况。 最后用异端推法放松一下。 $$[\dfrac {x^k} {k!}]\sum_{i=0}^n C(n,i)e^{ix}n^{n-i}$$ $$[\dfrac {x^k} {k!}](e^x+n)^n$$ $$[\dfrac {x^k} {k!}](e^x-1+n+1)^n$$ 注意到 $e^x-1$ 常数项为 $0$，要求第 $k$ 项，所以展开的时候只用展开到第 $k$ 项。 $$[\dfrac {x^k} {k!}]\sum_{i=0}^kC(n,i)(e^x-1)^i(n+1)^{n-i}$$ $$[\dfrac {x^k} {k!}]\sum_{i=0}^kC(n,i)\sum_{j=0}^i C(i,j)e^{jx}(-1)^{i-j}(n+1)^{n-i}$$ $$\sum_{j=0}^kj^kC(n,j)\sum_{i=j}^kC(n-j,i-j)(-1)^{i-j}(n+1)^{n-i}$$ 设 $t=-\dfrac 1 {n+1} \sum_{j=0}^kj^kC(n,j)(n+1)^{n-j}\sum_{i=0}^{k-j}C(n-j,i)t^i

设 f_j=\sum_{i=0}^{k-j}C(n-j,i)t^i，那么 f_j-f_{j+1}=

\sum_{i=0}^{k-j}C(n-j,i)t^i-\sum_{i=0}^{k-j-1}C(n-j-1,i)t^i t\sum_{i=0}^{k-j-2}C(n-j-1,i)t^i+C(n-j,k-j)t^{k-j} t(f_{j+1}-C(n-j-1,k-j-1)t^{k-j-1})+C(n-j,k-j)t^{k-j} tf_{j+1}+C(n-j-1,k-j)t^{k-j}

所以 f_j=(t+1)f_{j+1}+C(n-j-1,k-j)t^{k-j}，可以 O(k) 递推。

其他的简单处理一下，时间复杂度约为 O(k)。