[2018百度之星] 资格赛1005 序列计数 (DP, 树状数组, 随机)

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=820&pid=1005

这题随机给你一个1~n的排列，要你统计这1~n的排列中长度为1~n的上升子序列的个数分别是多少。

由于数据是随机的，因此这个序列中的LIS满足下面这个工作：

img

LIS的长度大概是$2\sqrt{N}$，当$N=10000$时，LIS的最长长度大约为$200$。

我们很容易就推出LIS的计数公式：
$$
f(i,k) += (p_i > p_j)? f(j,k-1) : 0
$$
可以考虑枚举LIS的长度$l$，用bit维护到第$i$个位置的数字$p[i]$、长度为$l-1$的上升子序列的总数，这样每次扫一个位置的时候，就可以直接查前缀和了。

由于要更新bit，所以维护一个滚动的dp数组，在查询长度为$l-1$的计数结果的同时，更新答案以及$l$的计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)

using LL = long long;
const LL maxn = 10100;
const LL mod = 1e9+7;
LL n;
LL p[maxn];
LL bit[maxn];
LL f[2][maxn];

LL lowbit(LL x) {
  return x & -x;
}

void add(LL x, LL val) {
  for(LL i = x; i <= n; i+=lowbit(i)) {
    bit[i] += val; bit[i] %= mod;
  }
}

LL sum(LL x) {
  LL ret = 0;
  for(LL i = x; i; i-=lowbit(i)) {
    ret += bit[i];
    ret %= mod;
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  LL T, _ = 0;
  scanf("%I64d", &T);
  while(T--) {
    scanf("%I64d", &n);
    for(LL i = 1; i <= n; i++) {
      scanf("%I64d",&p[i]);
    }
    memset(bit, 0, sizeof(bit));
    memset(f, 0, sizeof(f));
    LL x = 0, flag = 1;
    for(LL i = 1; i <= n; i++) f[0][i] = 1;
    printf("Case #%I64d:", ++_);
    printf(" %I64d", n);
    for(LL l = 2; l <= n; l++) {
      x = !x;
      LL ret = 0;
      if(flag) {
        memset(bit, 0, sizeof(bit));
        for(LL i = 1; i <= n; i++) {
          f[x][i] = sum(p[i] - 1);
          ret += f[x][i]; ret %= mod;
          add(p[i], f[!x][i]);
        }
      }
      if(ret == 0) flag = 0;
      printf(" %I64d", ret);
    }
    printf("\n");
  }
  return 0;
}