//Huyduocdithitp
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 105
#define endl '\n'
using namespace std;
bool ghuy4g;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
ll getbit(ll mask, ll i) {
return (mask >> i) & 1;
}
ll onbit(ll mask, ll i) {
return mask | (1 << i);
}
void add(ll &u, ll v) {
u += v;
if (u >= mod) u -= mod;
}
ll n, L, a[N];
ll f[N][N][1005][3];
ll dp(ll i, ll j, ll k, ll m) {
if (i > n) {
if (j == 1 && m == 2 && k <= L) return 1;
return 0;
}
if (i - 1 + j + 1 - m > n) return 0;
if (f[i][j][k][m] != -1) return f[i][j][k][m];
ll res = 0;
// case 1
if (1) {
ll new_j = j + 1, new_m = m;
ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
if (k + cost <= L) {
add(res, dp(i + 1, j + 1, k + cost, m));
}
}
// case 2
if (2 && m + 1 <= 2) {
ll base = 2 - m;
ll new_j = j + 1, new_m = m + 1;
ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
if (k + cost <= L) {
add(res, dp(i + 1, j + 1, k + cost, m + 1) * base % mod);
}
}
// case 3
if (3 && j - 1 >= 1) {
ll base = 1;
if (m == 2) {
if (i == n) base = 1;
else base = (j - 1) * (j - 2);
}
else if (m == 0) {
base = (j - 1) * j;
}
else if (m == 1){
base = (j - 1) * (j - 1);
}
ll new_j = j - 1, new_m = m;
ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
if (k + cost <= L) {
add(res, dp(i + 1, j - 1, k + cost, m) * base % mod);
}
}
// case 4
if (4) {
ll base = 2 * j - m;
ll new_j = j, new_m = m;
ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
if (k + cost <= L) {
add(res, dp(i + 1, j, k + cost, m) * base % mod);
}
}
// case 5
if (5 && m + 1 <= 2) {
ll new_j = j, new_m = m + 1;
ll base = 0;
if (m == 0) {
base = 2 * j;
}
else if (m == 1) {
if (i == n) {
base = 1;
}
else base = j - 1;
}
ll cost = (2 * (new_j) - new_m) * (a[i + 1] - a[i]);
if (k + cost <= L) {
add(res, dp(i + 1, j, k + cost, m + 1) * base % mod);
}
}
f[i][j][k][m] = res;
return res;
}
void sub2() {
if (n == 1) {
cout << 1;
exit(0);
}
memset(f, -1, sizeof(f));
sort(a + 1, a + 1 + n);
cout << dp(1, 0, 0, 0) << endl;
}
bool klinh;
signed main() {
faster;
cin >> n >> L;
a[n + 1] = inf;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
sub2();
cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |