10分：枚举然后check即可，check的过程稍微加速一下，一旦不满足就返回，否则会TLE。
20分：我们显然可以一边dfs一边check前面生成的序列是否合法，这样的数据就卡不掉了，复杂度接近答案的大小。
30分：其实我们并不关心是多少，只关心我们生成的序列，一共出现了多少种不同的数字，以及这些数字必须得是从开始连续的，比如，我们可以用来代表所有类似于类的序列，最后乘上组合数即可，所以在的过程中，记录一共用了多少种数字，以及哪些数字被用到了，稍微剪枝一下就可以了。
另外40分：考虑一个状压，我们每次填入相同数字到一个子集去，比如这个方案，我们可以先给位置填入，变成，然后再给第个位置填入数字变成，这个过程中，凡是填入的数字的LIS都是可以算出来的。
状态是：表示我考虑完了数字，填入了这个集合的方案数。
转移不表，复杂度，但是由于给定LIS数组的限制，严重卡不满。
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 998244353
using namespace std;
ll C[3005][3005];
void init()
{
C[0][0]=1;
for (int i=1;i<=3000;i++)
for (int j=0;j<=i;j++)
{
if (i==1 || j==0) C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
int n,m;
int a[21];
ll dp[1<<20][21]; //填了i种数字，填了哪些位置的方案数
void add(ll &x,ll y) {x=(x+y)%mod; return;}
int can(int sta,int nxt)
{
int mx=0;
for (int i=0;i<n;i++)
{
if ((sta>>i)&1) mx=max(mx,a[i]);
if ((nxt>>i)&1) if (a[i]!=mx+1) return 0;
}
return 1;
}
int main()
{
init();
cin>>n>>m;
for (int i=0;i<n;i++) cin>>a[i];
dp[0][0]=1;
for (int sta=0;sta<(1<<n);sta++)
for (int i=0;i<n;i++)
if (dp[sta][i])
{
int bu=(1<<n)-1-sta;
for (int S=bu;S!=0;S=(S-1)&bu)
if (can(sta,S))
{
add(dp[sta|S][i+1],dp[sta][i]);
}
}
ll ans=0;
for (int i=1;i<=n;i++) add(ans,dp[(1<<n)-1][i]*C[m][i]);
cout<<ans<<endl;
}
100分：考虑把状压转移子集的过程拎出来：表示的是，我正在考虑数字的填写，当前在从后向前考虑第个位置填不填数字，当前状态是的方案数。
转移不表，有一个小细节是，我们并不知道有没有用到，这样你可以选择加一个状态来表示是否用过了，也可以选择就这么下来，这样你得到的答案表示的是，最多用了个不同数字，构造出的序列满足LIS数组的方案数。
容斥一下：即是恰好使用了个数字的方案数了。
时间复杂度，需要滚动一下数组。
#include <bits/stdc++.h>
#define ll long long
#define maxn 3000005
#define mod 998244353
using namespace std;
ll C[3005][3005];
void init()
{
C[0][0]=1;
for (int i=1;i<=3000;i++)
for (int j=0;j<=i;j++)
{
if (i==1 || j==0) C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
int n,m;
int a[21];
int premax[1<<20];
void init2()
{
for (int sta=0;sta<(1<<n);sta++)
{
for (int i=0;i<n;i++)
if ((sta>>i)&1)
premax[sta]=max(premax[sta],a[i]);
}
}
int dp[2][22][1<<20];
ll ans[25];
void add(int &x,int y) {x=(x+y)%mod; return;}
void DP()
{
int now=0,nxt=1;
dp[now][n-1][0]=1;
for (int turn=1;turn<=n;turn++)
{
for (int i=n-1;i>=0;i--)
for (int sta=0;sta<(1<<n);sta++)
if (dp[now][i][sta])
{
int tmp=dp[now][i][sta];
//case1：不选
if (i) add(dp[now][i-1][sta],tmp);
else add(dp[nxt][n-1][sta],tmp);
//case2：选
if (((sta>>i)&1)==0 && premax[sta&((1<<i)-1)]+1==a[i])
{
if (i) add(dp[now][i-1][sta|(1<<i)],tmp);
else add(dp[nxt][n-1][sta|(1<<i)],tmp);
}
dp[now][i][sta]=0;
}
//此时dp[nxt][n-1][sta]就是选了最多turn个数的时候的方案数
ans[turn]=dp[nxt][n-1][(1<<n)-1];
swap(now,nxt);
}
ll tot=0;
for (int i=1;i<=n;i++)
{
for (int j=i-1;j>=1;j--)
{
ans[i]=(ans[i]+(-1*C[i][j]*ans[j]%mod)+mod)%mod;
}
tot=(tot+ans[i]*C[m][i]%mod)%mod;
}
cout<<tot<<endl;
}
int main()
{
cin>>n>>m;
for (int i=0;i<n;i++) cin>>a[i];
init(); init2();
DP();
}