「CF1349F」 Slime and Sequences

砸题选做

Description

定义一个正整数序列为好序列，当且仅当如果某个数 $k$ 出现过，那么一定有 $k−1$ 在最后一个 $k$ 的前面出现过。

对于所有 $i\in[1,n]$ ，求出 $i$ 在所有长度为 $n$ 好序列中出现次数的和

Easy Version $n \leq 5000$

Hard Version $n \le 10^5$

Solution

Easy Version

我们不好直接计算这种具有重复元素的序列的技术问题，考虑是否存在一个构造方式，使得序列可以映射到排列上。

我们令 $l_i$ 表示 $i$ 这个数在序列 $a$ 中出现的最早的位置， $r_i$ 表示这个数在序列中最后出现的位置，考虑题目中的限制，事实上就是 $r_i > l_i - 1$，考虑一种用排列构造序列的方法，我们按 $a_i$ 从小到大的顺序考虑，每次把 $a_i$ 相同的那些数的下标从大到小放到这个排列的最后。显然，两个不同的序列构造出的排列显然不同。而对于每个排列，我们可以从前往后每次找到一个极长的下降子串，这个下降子串中的所有数都对应着原序列中的位置，并且这些位置上的数大小都一样，是上一个极长串上的数的大小 +1(第一个串的数 1)，显然这样构造出的序列也是满足条件的，并且两两不同。我们构造出了一个长度为 $n$ 好的序列与长度为 $n$ 排列之间的双射。

现在考虑如何计算答案，我们令 $\left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$ 为 $n$ 个数，可以分成 $k + 1$ 个串的方案数 (事实上他就是欧拉数)，$ans_k$ 为 $k+ 1 $ 在所有好序列中的出现次数，有

$$ans_k = \sum_{i = \max(1,k)}^{n} \left \langle \begin{matrix} i\\k\end{matrix}\right \rangle \binom{n}{i}(n - i)!$$

意义就是我们枚举当前数的位置，这个数前面一定会分成 $k + 1$ 个串，然后后面的数没有限制再乘一个前 $i$ 个数从 $n$ 个数中选出的方案数，因为在每一中合法方案中，$k + 1$ 每出现一次，这个序列就会被算上一次，所以不重不漏的计算到了每个数的贡献。

而欧拉数是可以 $n^2$ 递推的，所以总复杂度 $O(n^2)$

• 欧拉数的递推

  假设我们现在计算出了 $\left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$ ，考虑把 $n + 1$ 插入到这个排列中

  1. $n + 1$ 插在最前面，显然会和第一段融合在一起， $\left \langle \begin{matrix} n +1\\k\end{matrix}\right \rangle += \left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$
  2. $n +1$ 插在最后面，显然他自己就是一个新的串，$\left \langle \begin{matrix} n +1\\k +1\end{matrix}\right \rangle += \left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$
  3. $n + 1$ 插在中间，并且是某两个串的分割处，这样的位置一共有 $k$ 个，显然 $n + 1$ 依然会和后面那个串融在一起，$\left \langle \begin{matrix} n + 1\\k\end{matrix}\right \rangle += k \times \left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$
  4. $n + 1$ 插在中间，并且在某个串的内部，不在交界处，这样的位置一共有 $n - 1 - k$ 个，这时 $n + 1$ 会把这个串分开成两个，$\left \langle \begin{matrix} n + 1\\k + 1\end{matrix}\right \rangle += (n - 1 - k) \times \left \langle \begin{matrix} n\\k\end{matrix}\right \rangle$

Hard Version

在上一个算法中，欧拉数的递推是在让我们无法承受，我们考虑用容斥的方法计算欧拉数。

我们令 $\begin{vmatrix}
n\\k
\end{vmatrix}$ 表示 $n$ 个数的排列至少有 $k + 1$ 个串的方案数，那么毛估估一下，$\left \langle \begin{matrix} n\\k\end{matrix}\right \rangle = \sum_{i = k}^{n}(-1)^{i-k}\binom{i}{k}\begin{vmatrix}
n\\i
\end{vmatrix}$（事实上用二项式反演可以得到同样的结果）

而现在的问题是如何计算 $\begin{vmatrix}
n\\k
\end{vmatrix}$，考虑设长度为一个串的方案数的生成函数为 $G(x)$，我们把 $k$ 个串拼在一起就是 $k$ 个串的答案了，由于是序列问题，所以我们还要乘一个组合数，用指数生成函数即可。而 $G(x)$ 显然为 ${0, 1, 1, 1, 1}$ （0个数组不成一个环），$\hat{G}(x) = e^x - 1$ ，那么 $\begin{vmatrix}
n\\k
\end{vmatrix} = n^{n-k}$

将得到的结果带回到上面的计算答案的式子中，由于原本的式子中存在一个 $\max$ ，我们将 $ans_0$ 特判掉，去掉 $\max$

$$\begin{split} ans_k &= \sum_{i = k}^{n}\binom ni (n - i)! \sum_{j = k}^{i}(-1)^{j-k}\binom{j}{k}\begin{vmatrix} i\\j \end{vmatrix}\\ &= \sum_{i = k}^{n}\binom ni (n - i)! \sum_{j = k}^{i}(-1)^{j-k}\binom{j}{k}i^{i - j}\\ &= \sum_{i = k}^{n}\binom ni (n - i)! i!\sum_{j = k}^{i}(-1)^{j-k}\binom{j}{k}[x^i](e^x - 1)^{i -j}\\ &= n!\sum_{i = k}^{n}\sum_{j = k}^{i}(-1)^{j-k}\binom{j}{k}[x^i](e^x - 1)^{i - j}\\ &= n!\sum_{j = k}^{i}(-1)^{j-k}\binom{j}{k}\sum_{i = j}^{n}[x^i](e^x - 1)^{i - j}\\ &= \frac{n!}{k!}\sum_{j = k}^{i}(-1)^{j-k}\frac{j!}{(j - k)!}\sum_{i = j}^{n}[x^i](e^x - 1)^{i - j}\\ \end{split}$$

我们令 $R(j) = \sum_{i = j}^{n}x^i^{i - j}$，上面的式子可以写成：

$$\begin{split} ans_k &= \frac{n!}{k!}\sum_{j = k}^{i}(-1)^{j-k}\frac{j!}{(j - k)!}\sum_{i = j}^{n}[x^j](e^x - 1)^{i - j}\\ &= \frac{n!}{k!}\sum_{j = k}^{i}\frac{(-1)^{j-k}}{(j - k)!}R(j)j!\\ \end{split}$$

这是一种特殊的卷积形式，可以很快的解决就是了。

问题来到了 $R(j)$ 如何快速的计算，我们发现在循环中每一次 $(e^x-1)$ 的次数都不一样，取的系数也不一样，如果不优化，我们无法摆脱 $O(n^2)$ 的计算，考虑如何优化。

$$\begin{split} R(j) &= \sum_{i = j}^{n}[x^i](e^x - 1)^{i - j}\\ &= \sum_{i = j}^{n}[x^j]\left(\frac{e^x - 1}{x}\right)^{i - j}\\ &= [x^j]\sum_{i = j}^{n}\left(\frac{e^x - 1}{x}\right)^{i - j}\\ &= [x^j]\sum_{i =0}^{n - j}\left(\frac{e^x - 1}{x}\right)^{i}\\ \end{split}$$

现在我们已经解决了系数的问题，我们令 $F(x) = \frac{e^x - 1}{x}$，将它带入上式，并且加一些小优化

$$\begin{split} R(j) &= [x^j]\sum_{i =0}^{n - j}\left(\frac{e^x - 1}{x}\right)^{i}\\ &= [x^j]\sum_{i = 0}^{n - j}F(x)^i\\ &= [x^j]\frac{1 - F^{n - j + 1}(x)}{1 - F(x)}\\ &= [x^j]\left(\frac{1}{1 - F(x)}-\frac{F^{n - j + 1}(x)}{1 - F(x)}\right)\\ \end{split}$$

这个式子的前半段 $\frac{1}{1 - F(x)}$ 看起来很能直接求逆，但问题是 $1 - F(x)$ 的常数为 0 ，不是很能做。于是我们从隔壁抽代那变的分式环理论中，把这个式子改成 $\frac{1}{(1 - F(x))x^{-1}}x^{-1}$ ，常数项就不是 0 了，毛估估一下应该是对的，毕竟拉格朗日差值也是用了这个理论的。

那么后半段怎么做呢？我们令 $S(k) = [x^k]\frac{F^{n - k + 1}(x)}{1 - F(x)}$，这个式子的问题依然是每次取的系数不一样，需要优化

$$\begin{split} S(k) &= [x^k]\frac{F^{n - k + 1}(x)}{1 - F(x)}\\ &= [x^{n + 1}]\frac{(xF(x))^{n - k + 1}}{1 - F(x)}\\ &= [x^{n + 1}][y^{n - k + 1}]\sum_{i = 0}\frac{(xF(x))^i}{1 - F(x)}\\ &= [x^{n + 1}][y^{n - k + 1}](\frac{1}{1 - F(x)}\cdot\frac{1}{1 - xF(x)y})\\ \end{split}$$

现在我们已经把 $S(k)$ 搞成了一个类似二元函数取某一项的形式了，看到二元函数，就会不自觉的想起像是拉格朗日反演这样的科技，但是我们要先构造出两个多项式 $G(x), H(x), W(x)$ 使得 $G(W(x)) = x, H(W(x)) = \frac{1}{1 - F(x)}\cdot\frac{1}{1 - xF(x)y}$ ，这样就可以快速算 $S(k)$ 了

这里提供一个构造方法，我们令 $W(x) = xF(x)$，并且设一个新的函数 $M(x)$，使得 $M(W(x)) = F(x)$，这样 $G(x) = \frac{x}{M(x)}$，便构造出了一个复合逆，同时我们要构造 $H(W(x)) = \frac{1}{1 - F(x)}\cdot\frac{1}{1 - xF(x)y}$ ，令 $H(x) = \frac{1}{1 - M(x)}\cdot\frac{1}{1 - xy}$，便满足了所有条件。

接下来的事就比较暴力了，我们网上套一个拉格朗日反演

$$\begin{split} [x^n]H(W(x)) = \frac1n[x^{n - 1}](H'(x)\left(\frac{x}{G(x)}\right)^n)\\ \end{split}$$

求个导得到 $H’(x) = \frac{y(1 - M(x)) + (1 - xy)M’(x)}{(1 - M(x))^2(1 - xy)^2}$ ，带入

$$\begin{split} [x^n]H(W(x)) &= \frac1n[x^{n - 1}](H'(x)\left(\frac{x}{G(x)}\right)^n)\\ &= \frac1n[x^{n - 1}]\left(\frac{y(1 - M(x)) + (1 - xy)M'(x)}{(1 - M(x))^2(1 - xy)^2}M(x)^n\right)\\ &= \frac1n[x^{n - 1}]\left(\frac{y}{(1 - M(x))(1 - xy)^2} + \frac{M'(x)}{(1 - M(x))^2(1 - xy)}\right)M(x)^n\\ \end{split}$$

由于我们求 $S(k)$ 要求这个函数的 $[y^m]$ 处的值，我们把这个式子关于 $y$ 的封闭形式全部展开，然后取出第 $m$ 项

$$\begin{split} [x^n]H(W(x)) &= \frac1n[x^{n - 1}]\left(\frac{y}{(1 - M(x))(1 - xy)^2} + \frac{M'(x)}{(1 - M(x))^2(1 - xy)}\right)M(x)^n\\ &= \frac1n[x^{n - 1}][y^m]\left(\frac{1}{1 - M(x)}\sum_{i=0}(i +1)x^iy^{i +1} + \frac{M'(x)}{(1 - M(x))^2}\sum_{i = 0}x^iy^i\right)M(x)^n\\ &= \frac1n[x^{n - 1}]\left(\frac{mx^{m - 1}}{1 - M(x)} + \frac{M'(x)}{(1 - M(x))^2}x^m\right)M(x)^n\\ &= \frac1n\left([x^{n - m}]\frac{mM(x)^n}{1 - M(x)} + [x^{n - m - 1}]\frac{M'(x)M(x)^n}{(1 - M(x))^2}\right)\\ \end{split}$$

问题来了， $M(x)$ 到底是什么？

因为 $G(W(x)) = G(e^x - 1) = x$，所以可以构造出 $G(x) = \ln(x+1)$，则 $M(x) = \frac{x}{G(x)} = \frac{x}{\ln(x + 1)}$

问题又来了，这个函数的常数又是 0，那我们依然抄上一个做法就好了，把式子整理一下，得

$$\begin{split} [x^n]H(W(x)) &= \frac1n\left([x^{n - m}]\frac{mM(x)^n}{1 - M(x)} + [x^{n - m - 1}]\frac{M'(x)M(x)^n}{(1 - M(x))^2}\right)\\ &= \frac1n[x^{n - m + 1}]\left(\frac{mM(x)^n}{(1 - M(x))x^{-1}} + [x^{n - m - 1}]\frac{M'(x)M(x)^n}{((1 - M(x))x^{-1})^2}\right)\\ \end{split}$$

毛估估一下，就做完了。