This problem is solved with dynamic programming. The state space is (T, i) where T is a set of cows and i is the index of a cow in T. Let f(T, i) represent the number of "Mixed Up" sequences using the cows in T such that the last cow in every sequence is i. Then f(T, i) equals the sum of f(T-i, k) over all k such that k is in T-i and |S[k]-S[i]| > K. This follows from the observation that the only restrictions on the index of the final cow in a "Mixed Up" sequence come from the index of the second-to-last cow in the sequence.
To implement this algorithm, use a bitmask b of length N to represent T: the i-th bit of b is set if and only if the cow with index i is in T. Then testing to see if cow i is in T is equivalent to testing if (b&(1<<i) == 1), and adding cow i to T is equivalent to (b = b|(1<<i)). There are O(2NN) states, each taking O(N) time to solve, for a total running time of O(2NN2).
/* LANG: C++ */ #include <stdio.h> #include <iostream> #define MAX 16 using namespace std; #define REP(i,n) for(int i=0;i<n;i++) typedef long long LL; int S[MAX]; LL ways[1<<MAX][MAX]; int main() { FILE *fin = fopen("mixup2.in", "r"), *fout = fopen("mixup2.out", "w"); int N, K; fscanf(fin, "%d %d", &N, &K); REP(i, N) fscanf(fin, "%d", &S[i]); REP(last, N) ways[1<<last][last] = 1; REP(mask, 1<<N) REP(last, N) if (mask&(1<<last)) REP(next, N) if ((mask&(1<<next)) == 0 && abs(S[next]-S[last]) > K) ways[mask|(1<<next)][next] += ways[mask][last]; LL res = 0; REP(last, N) res += ways[(1<<N)-1][last]; fprintf(fout, "%lld\n", res); return 0; }