原题地址
强烈吐槽百度使我的博客里第一次出现 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)$ 取模后的值,相邻的两个数中间用一个空格隔开,行末不要有多余空格。
样例
输入
2
4
1 2 3 4
4
1 3 2 4
输出
Case #1: 4 6 4 1
Case #2: 4 5 2 0
思路
首先我们可以想到一个暴力 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 题了。
代码
// Array_Division.cpp : Defines the entry point for the console application.
// XG_Zepto, 8/5/2018. All rights reserved.
#include
#include
#include
#include
#define mod 1000000007
#define maxn 10010
#define maxm 229
using namespace std;
int f[maxn][maxm],a[maxn],n;
struct BT{
int t[maxn];
void Add(int p,int x){while(p<=n) t[p]+=x,t[p]%=mod,p+=(p&-p);}
int sum(int p){int r=0;while(p)r+=t[p],r%=mod,p-=(p&-p);return r;}
}d[221];
int main(){
ios::sync_with_stdio(false);
int T;cin>>T;for (int i=1;i<=T;i++){
cout<<"Case #"<>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
d[1].Add(a[i],1);
f[i][1]=1;
if (i==1) continue;
for(int l=1;l<=min(maxm,n);l++){
int x=d[l].sum(a[i]-1);
if (!x) break;
f[i][l+1]=x%mod;
d[l+1].Add(a[i],x);
}
}
for(int l=1;l<=min(n,maxm);l++){
int tem=0;
for (int j=1;j<=n;j++)
tem=(tem+f[j][l])%mod;
cout<