MIXUP2 - Đàn bò hỗn loạn
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 17
typedef long long ll;
ll f[MAX][1<<MAX];
int n,k;
int a[MAX];
int lg2[1<<MAX];
int iabs(const int &x) {
if (x<0) return (-x); else return (x);
}
void init(void) {
scanf("%d",&n);
scanf("%d",&k);
int i;
for (i=0;i<n;i=i+1) scanf("%d",&a[i]);
for (i=0;i<MAX;i=i+1) lg2[1<<i]=i;
}
void optimize(void) {
int i,j,s,t;
for (i=0;i<n;i=i+1)
f[i][(1<<n)-1-(1<<i)]=1;
for (j=(1<<n)-1;j>=0;j=j-1)
for (i=0;i<n;i=i+1) {
if ((j|(1<<i))==j) continue;
s=j;
while (s>0) {
t=lg2[s&(-s)];
if (abs(a[t]-a[i])>k) f[t][j-(1<<t)]+=f[i][j];
s=s-(1<<t);
}
}
ll res=0;
for (i=0;i<n;i=i+1) res+=f[i][0];
printf("%lld",res);
}
int main(void) {
init();
optimize();
return 0;
}