#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;
inline void fileIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
constexpr int N = 100 + 10;
constexpr int L = 1010;
constexpr int MOD = 1e9 + 7;
template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }
int n , l;
ll dp[2][N][L][3], arr[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef LOCAL
// fileIO("forbidden1");
#endif
cin >> n >> l;
if (n == 1) return cout << 1 << endl, 0;
rep(i , 0 , n) cin >> arr[i];
sort(arr, arr + n);
rep(i , 0 , n)
arr[i] = arr[i + 1] - arr[i];
dp[0][1][arr[0] << 1][0] = 1;
dp[0][1][arr[0]][1] = 2;
rep(i , 0 , n - 1) {
int id = i & 1;
rep(j , 1 , i + 2) {
rep(z , 0 , l + 1) {
// sar o tah 0 baste
{
ll me = dp[id][j][z][0];
ll EN = 2 * j;
// merge
if (j > 1 && (EN - 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][0] , (j - 1) * me);
// sar ya tah
// endpoint bashe
if ((EN - 1) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][1] , 2 * me);
// on vasata bashe
if (EN * arr[i + 1] + z <= l)
add(dp[id ^ 1][j][EN * arr[i + 1] + z][0] , me * EN);
// jadid
if ((EN + 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][0] , me * (j + 1));
if ((EN + 1) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][1] , me * 2);
}
// sar o tah 1 baste
{
ll me = dp[id][j][z][1];
ll EN = 2 * j - 1;
// merge
if (j > 1 && (EN - 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][1] , (j - 1) * me);
// sar ya tah
// endpoint
if ((EN - 1) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][2] , me);
// on vasata
if (EN * arr[i + 1] + z <= l)
add(dp[id ^ 1][j][EN * arr[i + 1] + z][1] , me * EN);
// jadid
if ((EN + 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][1] , me * j);
if ((EN + 1) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][2] , me);
}
// sar o tah 2 baste
{
ll me = dp[id][j][z][2];
ll EN = 2 * j - 2;
// merge
if (j > 1 && (EN - 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][2] , (j - 1) * me);
// sar ya tah
// on vasata
if (EN * arr[i + 1] + z <= l)
add(dp[id ^ 1][j][EN * arr[i + 1] + z][2] , me * EN);
// jadid
if ((EN + 2) * arr[i + 1] + z <= l)
add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][2] , me * (j - 1));
}
}
}
memset(dp[id] , 0 , sizeof(dp[id]));
}
/*
rep(j , 1 , n + 1)
rep(z , 0 , l + 1) {
cout << j << ' '<< z << ' '<< dp[(n - 1) & 1][j][z][2] << endl;
} */
ll res = 0;
rep(i , 0 , l + 1) {
add(res , dp[(n - 1) & 1][1][i][2]);
}
cout << res << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
33 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5632 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5632 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
5632 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5632 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5632 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
33 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5632 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5632 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5632 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
5632 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
