记忆化搜索题，类似 DP 。

形式化题意：给定 $n$ 个数，求满足任意两个相邻的数差值大于给定数值的排列方案数。

看到排列一般会直接想到dfs，但 $n$ 是 $16$ 的，dfs $O(n!)$ 会 tle，显然过不了。但不难发现计算时会经常出现前面已经排好的方案不一样，但后面剩下还没排的数都一样的情况，此时就会出现大量重复计算。考虑到影响当前方案数的因素只有：已经排好了多少个、前面都有哪些参与了排列、当前排列的最后一个数是什么。因此记忆化搜索，用 $dp[k][state][last]$ 记录当前应该填第 $k$ 个数，已经填到了 $state$ 的状态（ $state$ 在二进制下哪些位上是 $1$ 就代表哪几个数已经用了）且最后一次填的下标为 $last$ 的方案数。那么就可以这样转移：

$$dp[k][state][last]=\sum dp[k+1][state|(1<<(i-1)][i],(state>>(i-1)\text{and}1)==1 $$

关于复杂度：最劣情况下，每一种 $state$ 被访问一次，对于每一种 $state$ ，每一个数字都有机会成为 $last$ （如果这个数字在 $state$ 下），然而 $state$ 确定了 $k$ 就确定了。因此 $O(n·2^n)$ ，而且不容易跑满。

最后不要忘记dfs的边界条件。 这道题就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=17;
int n,K;
int h[N];
int dp[N][(1<<N)][N];
inline int dfs(int k,int state,int last){
	if(k==n+1)return 1;
	if(dp[k][state][last])return dp[k][state][last];
	for(int i=1;i<=n;i++){
		if((state>>(i-1))&1||abs(h[i]-h[last])<=K)continue;
		dp[k][state][last]+=dfs(k+1,state|(1<<(i-1)),i);
	}
	return dp[k][state][last];
}
signed main(){
	n=re(),K=re();
	for(int i=1;i<=n;i++)h[i]=re();
	h[0]=-K-1;
	cout<<dfs(1,0,0);
	return 0;
}

SOLUTION

看到 $n \le 16$ 这个肯定是状压无疑了。

于是我们定义 $f_{S,i}$ 为选了 $S$ 里的元素，结尾为 $i$ 的方案数。

转移使用填表法比用刷表少一个 $n$，于是我们以 $popcount$ 枚举 $[0,2^n-2]$ 内的所有数，枚举其结尾元素，枚举下一个添加的元素，判断是否合法，然后直接加就行了，也不用取模。

复杂度 $O(2^n n^2)$。

注：笔者发现了一种神奇的方法，使用 $lowbit$ 运算加速了枚举，不知道有没有显著优化。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,k;
#define lowbit(x) (x&(-x))
int mp[65536];
int trans(int x){
    return mp[x];
}
int ppc(int x){
    int r=0;
    while(x) r+=(x&1),x>>=1;
    return r;
}
pair<int,int> p[65536];
int h[20];
int f[65536][17];
signed main(){
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>h[i];
		mp[1<<(i-1)]=i;
    }
    for(int i=0;i<(1<<n);i++){
        p[i]={ppc(i),i};
    }
    sort(p,p+(1<<n));
    for(int i=1;i<=n;i++){
        f[p[i].se][i]=1;
    }
    for(int i=1;i<(1<<n)-1;i++){
        int s=p[i].se,t=0;
        int S=p[i].se;
        while(s){
            t=trans(lowbit(s)),s-=lowbit(s);
            if(f[S][t]==0) continue;
            int r=p[i].se^((1<<n)-1),j;
            while(r){
                j=trans(lowbit(r)),r-=lowbit(r);
                if(abs(h[t]-h[j])<=k) continue;
                int T=(S|(1<<(j-1)));
                f[T][j]+=f[S][t];
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=f[(1<<n)-1][i];
    }
    cout<<ans<<'\n';
    return 0;
}