bzoj3591 最长上升子序列

Description

给出1~n的一个排列的一个最长上升子序列,求原排列可能的种类数。

Input

第一行一个整数n。

第二行一个整数k,表示最长上升子序列的长度。

第三行k个整数,表示这个最长上升子序列。

Output

第一行一个整数,表示原排列可能的种类数。

Sample Input

5
3
1 3 4

Sample Output

11

HINT

【样例说明】
11种排列分别为(1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4)。
【数据规模和约定】
对于30%的数据,1 <= n <= 11。
对于70%的数据,1 <= n <= 14。
对于100%的数据,1 <= n <= 15,答案小于2^31。

Source

2014年国家集训队十五人互测 By strongoier

题解

$O(n^2)$的$LIS$问题可以通过改变方程意义$f[i]$表示长度为$i$的结尾最小值。我们可以通过状压枚举单调栈的情况,其中$0$表示这个数没被考虑到,$1$表示这个元素已经被替换过了,$2$表示这个元素还在单调栈中

因此我们可以枚举当前状态的子集,因为子集一定可以替换掉全集$S$。

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
#include<cstdio>
using namespace std;
int n, m;
int x, pre[16], bin[23], st[1 << 15], g[15][1 << 15], cnt[1 << 15], tot;
int f[14349907];
int main() {
scanf("%d%d", &n, &m);
tot = 1 << n;
bin[0] = 1;
for(int i = 0; i < n; ++i) pre[i] = -1;
for(int i = 1; i < n; ++i)bin[i] = bin[i - 1] * 3;
for(int i = 1; i < (tot); ++i) cnt[i] = cnt[i >> 1] + (i & 1);
int last = -1;
for(int i = 1; i <= m; ++i) {
scanf("%d", &x);--x;
pre[x] = last;
last = x;
}
for(int S = 0; S < (tot); ++S)
for(int i = 0; i < n; ++i) if(!(S & 1 << i)){
if(cnt[S] > m) continue;
g[i][S] = S | 1 << i;
for(int j = i + 1; j < n; ++j)
if(g[i][S] & 1 << j) {
g[i][S] ^= 1 << j;
break;
}
} else st[S] += bin[i];
for(int i = 0; i < n; ++i)
if(pre[i] < 0) f[bin[i] << 1] = 1;
for(int S = 0; S < (tot); ++S)
for(int i = 0; i < n; ++i)
if(!(S & 1 << i)) {
if(pre[i] >= 0 && !(S & 1 << pre[i])) continue;
for(int t = S; t; t = (t - 1) & S) {
if(cnt[t] > m) continue;
if(f[st[S] + st[t]])f[st[S | 1 << i] + st[g[i][t]]] += f[st[S] + st[t]];
}
}
int ans = 0;
for(int S = 0; S < (tot); ++S)
if(cnt[S] == m)
ans += f[st[(tot) - 1] + st[S]];
printf("%d\n", ans);
return 0;
}