省选集训2023年2月9日T2

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

省选集训2023年2月9日T2

2023-02-10 16:57:58 来源：博客园

(资料图片仅供参考)

简要题意

给定 \(n, k\)，求所有长度为 \(n\) 的排列的逆序对个数的 \(k\) 次方之和。数据范围：\(1 \le n \le 10^{18}, 1\le k \le 1000\)。

思路

首先考虑如何处理 \(k\) 次方。注意到 \(k\) 很小而 \(n\) 的大小完全不能接受，所以我们需要一种和 \(k\) 有关而和 \(n\) 无关（或关系较小）的做法。考虑如果 \(k = 1\) 我们会怎么做，显然通过计算贡献可以很容易得出答案。这种做法本质上是依次考虑每个逆序对，而其它数的排列顺序不重要，所以直接用排列组合的方法计算出情况总数。如何扩展这种做法呢？考虑 \(x^k\) 有什么组合意义，一个最基本的想法是：从 \(x\) 物品中选 \(k\) 次（有放回，有顺序），所有的方案总数。并且当 \(k = 1\) 时它也确实等价于算贡献。因此这种转化是有前途的。这一思路得以优化时间复杂度的原理是：选择 \(k\) 次逆序对，所涉及到的元素至多有 \(2k\) 个，剩下的元素直接随意排列即可。所需处理的序列从 \(n\) 下降到了 \(k\) 级别。

根据上面的想法，设 \(f_{m, i}\) 表示长度为 \(m\) 的所有排列，选 \(i\) 次逆序对的选法总数，同时要求这 \(i\) 个逆序对涉及到的元素覆盖了排列中的全部的 \(m\) 个元素。这一要求是基于计算不重不漏的原则提出的。如果不要求这些逆序对涉及所有元素，那么那些没有被涉及的元素所产生的其他逆序对，就可能会在另一次计数中被选中。然而两次计数实际上对应同一（组）排列，就会重复计算。

假设我们已经算出了 \(f\)，则答案很容易表示为 \(\sum\limits_{m = 2}^{2k}{\binom{n}{m}^2(n - m)!f_{m, k}}\)，即我们首先计数被选出的逆序对涉及到的元素的关系构成的结构，然后在 \(n\) 个位置中选择 \(m\) 个放置它们，接着从 \(n\) 个元素中选择 \(m\) 个为它们赋值（注意 \(f\) 的计数过程中，只考虑了排列元素的大小关系，而没有计算它们具体取值的可能性），最后将剩下的 \(n-m\) 个元素随意排列（因为它们中的逆序对是不需要计数的——我们会在它们被选取为那特定的 \(k\) 个时计算它们的贡献）。

接下来，回头考虑怎么算 \(f\)。显然，强制要求每个点被选中是困难的，但是我们可以借助强大的工具——容斥。也即，考虑枚举一些点不被任何逆序对涉及到，而剩余的点必须被涉及到（这可以借助递推来做到）。具体地，首先设 \(g\) 为长度为 \(m\) 的所有排列选 \(i\) 次逆序对，并且没有任何限制的方案总数。显然有初始条件 \(f_{0, 0} = 1, f_{1, 0} = f_{0, i} = f_{1, i} = 0; g_{0, 0} = g_{1, 0} = 1, g_{0, i} = g_{1, i} = 0 (i > 0)\)。接下来计算 \(g\) 的递推，有 \(g_{m, i} = \sum\limits_{j = 0}^{i}g_{m - 1, i - j}\sum\limits_{t = 0}^{m - 1}t^j\)。设 \(s_{m, j} = \sum\limits_{t = 0}^{m - 1}t^j\)，可以在 \(\Theta(k^2\log k)\) 内直接算出来。接下来每一行都是一个关于上一行和 \(s\) 序列的卷积，直接NTT，时间复杂度 \(\Theta(k^2\log k)\)。随后再考虑 \(f\) 的计算，根据上述容斥，有 \(f_{m, i} = g_{m, i} - \sum\limits_{j = 0}^{m - 1}\binom{m}{j}^2(m - j)!f_{j, i}\)。这个东西正常我们是需要分治NTT的，但是考虑到我们只需要 \(i = k\) 的 \(f\)，所以直接暴力 \(\Theta(k^2)\)，甚至没到复杂度瓶颈上。

最后一点需要注意的是，这题需要求 \((n - m)!\)，这个东西似乎不好算也不好避开，但是考虑到当 \(n \ge 998244353\) 时答案算出来总是 \(0\)，所以直接预处理 \(10^9\) 以内的阶乘，每 \(10^6\) 个分成一块打成表，就可以算了。

代码

暂无

关键词：这个东西时间复杂度