原题地址

强烈吐槽百度使我的博客里第一次出现 http 链接。

题意概述

你有一个长度为 n 的随机排列,求它的不同长度的上升子序列的个数。

输入与输出

输入

第一行包含一个整数 $T$,表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据:

第一行包含一个整数 $n$,表示排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2 , …, p_n$,表示排列的 $n$ 个数。

保证 $1 leq T leq 100$,$1 leq n leq 10^4$,$T$ 组测试数据的 $n$ 之和 $leq 10^5$,$p_1,p_2,…,p_n$ 是 $1,2,…,n$ 的一个排列。

除了样例,你可以认为给定的排列是从所有 $1,2,…,n$ 的排列中等概率随机选出的。

输出

对于每组测试数据,输出一行信息 $Case #x: c_1 c_2 c_n$,其中 $x$ 表示这是第 $x$ 组测试数据,$c_i$ 表示长度为 $i$ 的上升子序列个数对 $1000000007(=10^9+7)$ 取模后的值,相邻的两个数中间用一个空格隔开,行末不要有多余空格。

样例

输入

输出

思路

首先我们可以想到一个暴力 DP 的方法。令 $f_{i,j}$ 为以 $a_i$ 结尾,长度为 $j$ 的上升子序列个数。令 $p$ 满足 $i>p$ 且 $a_i>a_p$,有 $f_{i,j}= sum f_{p,j-1}$。显然,如果你枚举所有可能的 $i,j,p$ ,复杂度是 $O(N^3)$ 的,显然会超时。

但是我们敏锐地注意到,题目中强调多次排列是随机生成的,而对于随机排列,最长上升子序列的长度期望是 $sqrt N$。也就是说,方程中 $j$ 大概率不会超过这个值。实测枚举至 230 即可通过。

单单这样优化还不够。我们又发现,每一次转移都是前缀和的形式,那么我们可以开 $sqrt N$ 个树状数组,每计算一个 $f_{i,j}$ 都将其插入进去,就可以把转移优化至 $logN$。

现在我们获得了一个 $O(N logN sqrt{N} )$ 的算法,可以愉快地 A 题了。

代码