Description：

给出 $1\sim n$ 的一个排列的一个最长上升子序列，求原排列可能的种类数。

$1\leqslant n\leqslant 15$

Solution：

我们考虑用单调栈求 $LIS$ ，我们对于每个数记录他还没有被考虑 $(0)$ ，在栈里 $(1)$ ，出栈 $(2)$ ，然后把他按三进制状压乘一个数 $state$ ，因为栈是单调的，我们可以还原出这个栈，因此这个数就已经能够表示我们当前所知的所有信息，然后我们大力枚举下一个还没被考虑的数转移就行了，但是这里还有一个问题，就是原排列可能有多个最长上升子序列，然后有一个结论吧，就是只要顺序对了，那么所有长为 $m$ 的 $LIS$ 都可以对应给出的 $LIS$ ，然后就可以计数了。我也不知是为啥。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 17

int lis[MAXN];

unsigned int f[15000000];

int pow3[MAXN];

inline int bit(int x,int k){return x / pow3[k - 1] % 3;}

int stack[MAXN],top = 0;

int pre[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)pre[lis[i] = rd()] = i - 1;

	f[0] = 1;

	int tot = pow(3,n) - 1;

	pow3[0] = 1;for(register int i = 1;i <= n;++i)pow3[i] = pow3[i - 1] * 3;

	int ans = 0;

	for(register int i = 0;i <= tot;++i)

	{

		if(f[i] == 0)continue;

		register int done = 0;

		for(register int x = 1;x <= n;++x)if(bit(i,x))++done;

		if(done == n)

		{

			ans += f[i];

			continue;

		}

		top = 0;

		for(register int x = 1;x <= n;++x)if(bit(i,x) == 1)stack[++top] = x;

		stack[top + 1] = 0x3f3f3f3f;

		for(register int x = 1,cur = 1;x <= n;++x)

		{

			if(bit(i,x) == 0)

			{

				if(pre[x] && bit(i,lis[pre[x]]) == 0)continue;

				register int nxt = i;

				while(x > stack[cur])++cur;

				if(cur > m)continue;

				if(cur <= top)nxt += pow3[stack[cur] - 1];

				nxt += pow3[x - 1];

				f[nxt] += f[i];

			}

		}

	}

	cout << ans << endl;

	return 0;

}