#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
template<unsigned M_> struct modnum {
static constexpr unsigned M = M_;
using ll = long long; using ull = unsigned long long; unsigned x;
constexpr modnum() : x(0U) {}
constexpr modnum(unsigned x_) : x(x_ % M) {}
constexpr modnum(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr modnum(ull x_) : x(x_ % M) {}
constexpr modnum(ll x_) : x(((x_ %= static_cast<ll>(M)) < 0) ? (x_ + static_cast<ll>(M)) : x_) {}
explicit operator int() const { return x; }
modnum& operator+=(const modnum& a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
modnum& operator-=(const modnum& a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
modnum& operator*=(const modnum& a) { x = unsigned((static_cast<ull>(x) * a.x) % M); return *this; }
modnum& operator/=(const modnum& a) { return (*this *= a.inv()); }
modnum operator+(const modnum& a) const { return (modnum(*this) += a); }
modnum operator-(const modnum& a) const { return (modnum(*this) -= a); }
modnum operator*(const modnum& a) const { return (modnum(*this) *= a); }
modnum operator/(const modnum& a) const { return (modnum(*this) /= a); }
modnum operator+() const { return *this; }
modnum operator-() const { modnum a; a.x = x ? (M - x) : 0U; return a; }
modnum pow(ll e) const {
if (e < 0) return inv().pow(-e);
modnum x2 = x, xe = 1U;
for (; e; e >>= 1) {
if (e & 1) xe *= x2;
x2 *= x2;
}
return xe;
}
modnum inv() const {
unsigned a = x, b = M; int y = 1, z = 0;
while (a) {
const unsigned q = (b/a), c = (b - q*a);
b = a, a = c; const int w = z - static_cast<int>(q) * y;
z = y, y = w;
} assert(b == 1U); return modnum(z);
}
friend modnum inv(const modnum& a) { return a.inv(); }
template<typename T> friend modnum operator+(T a, const modnum& b) { return (modnum(a) += b); }
template<typename T> friend modnum operator-(T a, const modnum& b) { return (modnum(a) -= b); }
template<typename T> friend modnum operator*(T a, const modnum& b) { return (modnum(a) *= b); }
template<typename T> friend modnum operator/(T a, const modnum& b) { return (modnum(a) /= b); }
explicit operator bool() const { return x; }
friend bool operator==(const modnum& a, const modnum& b) { return a.x == b.x; }
friend bool operator!=(const modnum& a, const modnum& b) { return a.x != b.x; }
friend ostream &operator<<(ostream& os, const modnum& a) { return os << a.x; }
friend istream &operator>>(istream& in, modnum& n) { ull v_; in >> v_; n = modnum(v_); return in; }
};
using mint = modnum<mod>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, L;
cin>>n>>L;
if(n == 1){
cout<<"1\n";
}
vector<int>a(n+1);
for(int i=0;i<n;i++) cin>>a[i];
a[n] = 10000;
sort(a.begin(), a.end());
vector<vector<array<mint, 3>>>dp(n+2, vector<array<mint, 3>>(L+1)), ndp = dp;
dp[0][0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=L;k++){
for(int l=0;l<=2;l++) ndp[j][k][l] = 0;
}
}
for(int j=1;j<=i;j++){
for(int k=0;k<=L;k++){
for(int l=0;l<=2;l++){
int d = (2 * j - l) * (a[i] - a[i-1]);
if(k < d || i + j + 1 - l > n) continue;
ndp[j][k][l] += dp[j-1][k-d][l];
if(l) ndp[j][k][l] += (3 - l) * dp[j-1][k-d][l-1];
ndp[j][k][l] += (2 * j - l) * dp[j][k-d][l];
if(l == 1) ndp[j][k][l] += 2 * j * dp[j][k-d][l-1];
else if(l == 2){
if(i == n) ndp[j][k][l] += dp[j][k-d][l-1];
else if(j > 1) ndp[j][k][l] += (j - 1) * dp[j][k-d][l-1];
}
if(l == 2){
if(i == n) ndp[j][k][l] += dp[j+1][k-d][l];
else ndp[j][k][l] += j * (j - 1) * dp[j+1][k-d][l];
}
else if(l == 1) ndp[j][k][l] += j * j * dp[j+1][k-d][l];
else ndp[j][k][l] += j * (j + 1) * dp[j+1][k-d][l];
}
}
}
swap(dp, ndp);
}
mint ans = 0;
for(int k=0;k<=L;k++) ans += dp[1][k][2];
cout<<ans<<"\n";
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
324 KB |
Output is correct |
| 7 |
Correct |
0 ms |
328 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
