给定一个排列和 k=\Theta(n)，求排列中求长度为 k 的上升子序列数量（对常数 p 取模），可以做到 O(n^{1.99}) 吗？
我想这是个十分自然的问题，第一反应当然是“不行”，但是为什么？
我也很好奇，因此我向神提问。神说：不行，有条件下界。以下是由我转述的神的解答。省流是，排列长度为 k 的上升子序列计数和 \tilde O(n) 条边的 DAG 中长度为 k 的路径计数可以相互归约。
可以将这个问题归约到这样一个假设：
对于任意常数 \epsilon>0，存在常数 h，使得判定 m 条边的有向图中是否存在长度为 h 的环不存在 O(m^{2-\epsilon}) 的算法。这被称为 h-cycle 假设。
首先，在上述假设下，数一个 m 条边的 DAG s\to t 的长度为 k 的路径也是难以做到 O(m^{1.99}) 的。对原图的点以 1\sim h 随机染色分层，钦定一个环的顺序是 1\to 2 \to \dots \to h\to 1，由于 h 是常数所以每次有常数正确率。还需要把环转为路径，把第一层复制一遍接在最后，然后把第一层和最后一层以同样顺序造一条链，s 是第一层的链首，t 是最后一层的链尾，这样每个环都恰好对应图中 s\to t 的长度为 h 加上第一层点数减一的路径。
然后将一般 DAG 的定长路径计数归约到排列。把排列的计数看成它的 dp 形式，即维护了一个 dp 数组，每个元素是个生成函数，每次操作可以选定一个空位置，把小于它的加起来再加一再乘上 x。
而在一般 DAG 上我们的操作是选若干个生成函数加起来再乘上 x。由于 p 是常数，我们可以用 k=O(1) 个递减的数模拟出系数 k。于是考虑在每个当前存储的生成函数后面都塞一个其符号取反。那么每次操作的时候先在需要读取的生成函数的两个元素之间放一次，然后新增一个最大的元素作为操作得到的生成函数，还需要抵消掉加一的影响。最后需要从前往后抵消掉读取生成函数的影响。因为求和了两次，所以实际上一个长度等于 x^2。最后全部读取一下即可。
有个细节是环的个数可能恰好是 p 的倍数。可以非常暴力地随机以 1/2 概率保留每条边，再做 O(2^h) 次。