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;
}