题意
给出一个元素不重复，长为n<=15的序列的最长上升子序列之一。
求有多少个序列满足有这个最长上升子序列。
分析
这tm也是一题玄学题。
因为n=15，考虑状压，dp.
一个序列只要满足两个条件就是合法序列： 1)最长上升子序列长度为k，2)子序列存在于原序列中。
第二个好求，直接状压。
问题是第一个。
因为我们要求最长上升子序列的长度，所以状态里要带一个dp时的f数组
这样超时。
想一想求最长上升子序列的n log n算法，我们发现只需要存一个长度为i的上升子序列的最小结尾元素 也就是“辅助栈”就可以更新序列最长上升子序列的长度了。
但是怎么存？
因为辅助栈是单调的，所以只需要知道每个数有没有在辅助栈里出现就好了。
于是我们状态就有了，一个三进制的压位状态。 0表示没有出现过，1表示出现过，2表示出现过并且在辅助栈内。
转移比较显然，但需要加几个优化。
1）转移时注意到，因为x从小到大枚举，所以更新指针也会往前指。复杂度是O(n)的
2）找一下合法的一个必要条件优化： 因为a[i]是最长上升子序列中第i位，所以他前面不应该存在一个数x使得x<=a[i]且f[x]>=i.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 16
using namespace std;
int f[14348908];
int n,k,a[N],g[N],app[N],t,su[N];
int m[N],ans,stm;
void dfs(int x,int cnt,int st) {
if (x>n) {
if (f[st]==0) return;
++stm;
g[0]=0;
int s=st,nst=0,now=0;
for (int i=1; i<=n; i++) {
int yss=s/3,ys=s-yss*3;
if (ys!=0) app[i]=stm;
if (ys==2) g[++g[0]]=i;
s=yss; if (s==0) break;
}
for (int x=1; x<=n; x++) if (app[x]!=stm) {
if (su[x]>1 && app[a[ su[x]-1 ]]!=stm) continue;
while (now<g[0] && g[now+1]<x) now++;
bool bz=0;
for (int i=1; i<=k; i++)
if (app[a[i]]!=stm && a[i]>x && now+1>=i) {
bz=1; break;
}
if (bz==1) continue;
if (now==0 && g[1]<now) nst=st+m[x]; //0->1
else if (now!=g[0]) {
nst=st+m[x]*2; //0->2
nst=nst - m[g[now+1]]; //2->1
} else nst=st+m[x]*2;//0->2
f[nst]+=f[st];
if (t==n-1 && g[0]+(now==g[0])==k) ans=ans+f[st];
}
return;
}
if (n-x+1>t-cnt) dfs(x+1,cnt,st*3);
if (cnt<t) {
dfs(x+1,cnt+1,st*3+1);
dfs(x+1,cnt+1,st*3+2);
}
}
int main() {
freopen("sword.in","r",stdin);
freopen("sword.out","w",stdout);
cin>>n>>k;
m[1]=1; for (int i=2; i<=n; i++) m[i]=m[i-1]*3;
for (int i=1; i<=k; i++) scanf("%d",&a[i]),su[a[i]]=i;
if (k==1) {
cout<<1<<endl;
return 0;
}
f[0]=1;
for (t=0; t<n; t++) dfs(1,0,0);
cout<<ans<<endl;
}