【百度之星 2018 资格赛】序列划分 / 题解

原题地址

强烈吐槽百度使我的博客里第一次出现 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<