「营业日志 2020.12.10」Jiangly 的排列数数题
Elegia
·
·
个人记录
问对于所有长为 n 的排列，有多少排列存在一个连续上升段 \ge k。对所有 k 回答，对大质数取模。
首先经过转化，只需要数所有连续段均 <k 的即可。容易想到容斥，我们可以先假设有一些基本单位，然后容斥掉它们拼起来的情况，可得基本单位是 \frac{x-x^k}{1-x}，其容斥单位为
\begin{aligned}
&\quad 1-\frac 1{1+\frac{x-x^k}{1-x}}\\
&= 1-\frac{1-x}{1-x^k}\\
&= \frac{x-x^k}{1-x^k}\\
&= \sum_{j\ge 0} \left(x^{jk+1} - x^{(j+1)k}\right)
\end{aligned}
而排列实际的拼接是 EGF 的形式，因此答案为
n![x^n] \frac 1{\displaystyle1 - \sum_{j\ge 0} \left( \frac{x^{jk+1}}{(jk+1)!} - \frac{x^{(j+1)k}}{[(j+1)k]!}\right)}
由于下面的项数有 \Theta(n/k) 项，因此暴力求逆的复杂度为 \Theta(n^2/k)，求所有的答案是 \Theta(n^2\log n)。
能不能再给力一点啊？
注意到我们实际上有两个算法，一个算法是 \Theta(n\log n) 的求逆，一个算法是 \Theta(n^2/k) 的暴力求逆。那么我们显然应该选择当前最快的算法来跑。对于 k\le \frac n{\log n} 的时候是 \Theta(n\log n) 更快一点，所以对于前 \frac n{\log n} 项，总共复杂度为 \Theta(n^2)。而对于后面的来说，根据调和级数更加精确的分析：H_n = \ln n + \gamma + O(1/n)，因此从 \frac n{\log n} 到 n 求和，大约是 \log n - \log(n/\log n) = \log\log n，因此将这两个算法混在一起使用，复杂度就降到了 \Theta(n^2\log\log n)。（by Jiangly）
能不能再给力一点啊？
这个问题的 \Omega(n^2) 的 bound，是不可突破的吗？
我们刚刚实际上不仅求出了 k=1\sim n，还求出了更小的 n 的所有答案。但实际上我们并没有必要这么做。现在我们不妨假设有一个算法，他能在 \Theta((n/k)^c) 的复杂度内计算一个 k 对应的答案。容易发现在任何 k 的位置，\Theta(n^2/k) 的算法都是不占优的，因为若 k>\frac n{\log n}，那么 (n/k)^c < (\log n)^c \ll n < n^2/k。因此我们只需在 k\le n^{1-1/c}(\log n)^{-1/c} 的部分使用 \Theta(n\log n) 的算法，剩下的部分使用 \Theta((n/k)^c) 的算法。估界有
\begin{aligned}
&\quad \sum_{k>L} \left(\frac nk\right)^c\\
&< \int_L^\infty n^cx^{-c} \,\mathrm dx\\
&= \left.\frac 1{1-c}n^c x^{1-c}\right|_{x=L}^\infty\\
&= \frac 1{c-1}n^cL^{1-c},\quad L=n^{1-1/c}(\log n)^{-1/c}\\
&= \frac 1{c-1} n^{2-1/c}(\log n)^{1-1/c}
\end{aligned}
回顾我们要求的，无非是
n![x^n] \frac 1{1-x-x^{k+1}A(x^k)-x^kB(x^k)}
经过这样的改写，我们不难考虑枚举三个部分的次数，显然这等价于如此求和：
\sum_{u,v,w\ge 0} \binom{u+v+w}{u,v,w} U^uV^vW^w
而我们提取系数 [x^n]，这就固定了 x 项的次数，也就有
\begin{aligned}
&\quad [x^n] \frac 1{1-x-x^{k+1}A(x^k)-x^kB(x^k)}\\
&= [x^n]\sum_{u,v,w\ge 0} \binom{u+v+w}{u,v,w}x^{u(k+1)+vk+w}A(x^k)^uB(x^k)^v\\
&= [x^n]\sum_{u,v,w\ge 0} \binom{u+v+w}{u,v,w} [x^{n-u(k+1)-vk-w}] A(x^k)^uB(x^k)^v
\end{aligned}
此时 A(x^k)^uB(x^k)^v 只有 k 的倍数次才有值，因此维护和求值都是只关于 n/k 的。
如使用暴力卷积，那么复杂度为 \Theta((n/k)^4)，总复杂度是 \Theta(n^{7/4}(\log n)^{3/4})。
如这里使用 FFT，那么复杂度为 \Theta((n/k)^3\log (n/k))，总复杂度是 \Theta(n^{5/3}\log n)。
关于「能不能再给力一点啊？」这件事，先鸽着，以后再说（