9.9 T4 bubble sort

Vision271 · 2022-09-13 20:41:50 · 个人记录

题意

• 如果一个 1\sim n 的排列的 len_{LIS}\geqslant n-1，那么我们称它是“几乎正确的”。

• 给定 n,k，求有多少 1\sim n 的排列，满足其在冒泡排序 k 趟后是“几乎正确的”。

数据范围

解析

• 找一下冒泡排序的性质：

• 从这出发，考虑一下，完全正确的序列有什么要求？

  • ...

• 看到这个东西明显是一个 (k+1)^t 的形式。考虑手模一组样例吧，譬如 n=5,k=2，结果序列为 12345。

• 于是 1 在前 3，2 在前 4，3 在前 5，4 在...

• 前 5。发现对于较大的数字，它可能没有 k+1 个地方可放（得考虑顶满 n 个的问题）。

• 具体来讲，前 n-k 个数，后面（包括自己）都有至少 k+1 个位置可放；后 k 个数则分别有 k,k-1,\dots,1 个位置可放。

• 故总方案数应该为 (k+1)^{n-k}\times k!。

• 考虑把这个结论推广到 len_{LIS}=n-1 的情况。

  • 注意到，此时的最终序列相当于把完全正确的序列中某个数字抽出来，再任意地找一个地方插回去。

  • 于是发现，除了抽出位和插入位中间那一段，其他地方的数字其实没变。

  • 考察那一段，显然只分两种情况：取右放左或取左放右（放回原来位置那种事情不要啊）。

  • 用更数学语言的方式来描述，就是选择一段进行循环左移/右移。这里认为不考虑循环时的下标减小是左移。

• 首先考虑循环左移的情况，譬如 n=7,k=2，结果序列...譬如就 1342567 吧。循环左移 2\sim 4 位。

  • 手推。1 在前 3，3 在前 4，4 在前 5，2 在...前 6？

  • 发现这里 2 不能进前 5，否则导致排序后第 3 位为 2。 但 2 又不能出前 6，否则换不过来了。

  • 于是 2 的位置唯一。继续考察后面的数字，发现和之前没有本质区别，还是后包前，仍为 k+1 或退化成 k! 之一，故这一结果序列的初始序列总方案数为 (k+1)^{n-k-1}\times k!。

• 然后考虑循环右移的情况，譬如 n=7,k=2,1423567。

  • 简单手推发现，4 及前面不变，4 的后一个到循环位移段的最后一个（3）只有唯一的位置选择（必须在新增的那一个位置，否则会挤开较大的数跑到较小位上），后面本质不变（因为前面对空格的占用没有变）。

  • 故这一结果序列的初始序列的总方案数为 (k-1)^{n-k-len+1}\times k!。

  • 稍等！万一循环段和那个 k! 冲突呢？

  • 不会。最后 k+1 个元素是定死的，不允许动他们。

• 所以枚举 len 即循环位移段的长度求解。注意，len=1 的情况可以认为不存在，len=2 时左移和右移同构，且永远不许碰后 k 位，k=n-1 时一定只能完全正确，哪一位都不许碰。

• 复杂度 O(Tn)。

• 当然，循环左移可以等差数列求和，循环右移,,,嗯...本质上也就是等差乘等比吧，按道理讲...可以求和的。嗯，可以的。所以可以加速到 O(T\log n)。