#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// #pragma GCC optimize("Ofast,unroll-loops,inline")
// #pragma GCC target("avx2,bmi2,lzcnt")
#define pb push_back
#define all(x) x.begin(), x.end()
// #define int ll
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn = 20;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;
const int LOG = 21;
int n, L, a[maxn], b[maxn], dp[(1 << 20)][20][120];
int main() {
fast_io;
cin >> n >> L;
if (n == 1) {
cout << 1 << '\n';
return 0;
}
for(ll i = 0; i < n; i ++)
cin >> a[i];
if (n < 9) {
for(ll i = 0; i < n; i ++)
b[i] = i;
ll ans = 0;
while(true) {
ll dif = 0;
for (ll i = 1; i < n; i ++)
dif += abs(a[b[i]] - a[b[i - 1]]);
if (dif <= L)
ans ++;
if (next_permutation(b, b + n))
ans = ans;
else
break;
}
return cout << ans << "\n", 0;
}
for (int msk = 0; msk < (1 << n); msk++) {
if (__builtin_popcount(msk) == 1)
continue;
if (__builtin_popcount(msk) == 2) {
vector <ll> per;
for(ll i = 0; i < n; i ++){
if ((1 << i) & msk)
per.pb(i);
}
ll d = abs(a[per[0]] - a[per[1]]);
if(d > L)
continue;
dp[msk][per[0]][d] = 1;
dp[msk][per[1]][d] = 1;
continue;
}
for (int i = 0; i < n; i++) {
if (((1 << i) & msk) == 0) continue;
for (int j = 0; j < n; j++) {
if (((1 << j) & msk) ==0) continue;
if (j == i) continue;
for (int l = 0; l <= L; l++) {
if (l + abs(a[i] - a[j]) > L) continue;
dp[msk][i][l + abs(a[i] - a[j])] += dp[msk ^ (1 << i)][j][l];
dp[msk][i][l + abs(a[i] - a[j])] %= mod;
}
}
}
}
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int cost = 0; cost <= L; cost++) {
ans += dp[(1 << n) - 1][i][cost];
ans %= mod;
}
}
cout << ans << '\n';
}
Compilation message (stderr)
/tmp/ccrJjpvZ.o: in function `main':
skyscraper.cpp:(.text.startup+0x13): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x33): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x3d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x48): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x58): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x77): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0xa6): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x118): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x23b): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccrJjpvZ.o
skyscraper.cpp:(.text.startup+0x2c7): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
