#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;
template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define rep0(a) for (ll i = 1; i <= a; ++i)
#define rep1(i, a) for (ll i = 1; i <= a; ++i)
#define rep2(i, a, b) for (ll i = a; i <= b; ++i)
#define rep3(i, a, b, c) for (ll i = a; i <= b; i+=c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define repd0(a) for (ll i = a; i >= 1; --i)
#define repd1(i, a) for (ll i = a; i >= 1; --i)
#define repd2(i, a, b) for (ll i = b; i >= a; --i)
#define repd3(i, a, b, c) for (ll i = b; i >= a; i-=c)
#define repd(...) overload4(__VA_ARGS__, repd3, repd2, repd1, repd0)(__VA_ARGS__)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert
template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const char nl = '\n';
const int MX = 110;
ll modmul(ll a,ll b,ll mod){
ll res=(a*b-ll(1.l*a*b/mod)*mod)%mod;
if(res<0)res+=mod;
return res;
}
ll modinv(ll a, ll b) {
ll x=0,x1=1;
while(a!=0){
ll q=b/a;
b-=q*a; x-=q*x1;
swap(a,b); swap(x,x1);
}
return x;
}
template<ll M>
struct Mint {
ll x;
constexpr Mint():x(0){}
constexpr Mint(ll x):x(norm(x%getMod())){}
static ll Mod;
constexpr static ll getMod() {return M>0?M:Mod;}
constexpr static void setMod(ll Mod_) {Mod=Mod_;}
constexpr ll norm(ll x) const {if(x<0)x+=getMod(); if(x>=getMod())x-=getMod(); return x;}
explicit constexpr operator ll()const{return x;}
constexpr Mint operator-()const {Mint res; res.x=norm(-x); return res;}
constexpr Mint inv()const{return modinv(x, getMod());}
constexpr Mint &operator+=(const Mint &rhs) {x=norm(x+rhs.x); return *this;}
constexpr Mint &operator-=(const Mint &rhs) {x=norm(x-rhs.x); return *this;}
constexpr Mint &operator*=(const Mint &rhs) {x=modmul(x, rhs.x, getMod()); return *this;}
constexpr Mint &operator/=(const Mint &rhs) {x=modmul(x, rhs.inv().x, getMod()); return *this;}
constexpr Mint &operator++(){return *this+=1;}
constexpr Mint &operator--(){return *this-=1;}
constexpr Mint operator++(int) {Mint res=*this; *this+=1; return res;}
constexpr Mint operator--(int) {Mint res=*this; *this-=1; return res;}
friend constexpr Mint operator+(Mint lhs, const Mint &rhs) {return lhs+=rhs;}
friend constexpr Mint operator-(Mint lhs, const Mint &rhs) {return lhs-=rhs;}
friend constexpr Mint operator*(Mint lhs, const Mint &rhs) {return lhs*=rhs;}
friend constexpr Mint operator/(Mint lhs, const Mint &rhs) {return lhs/=rhs;}
friend istream &operator>>(istream &is, Mint &o) {ll x{}; is>>x; o=Mint(x); return is;}
friend ostream &operator<<(ostream &os, const Mint &o) {return os<<o.x;}
friend constexpr bool operator==(const Mint &lhs, const Mint &rhs) {return lhs.x==rhs.x;}
friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs) {return lhs.x!=rhs.x;}
friend constexpr bool operator<(const Mint &lhs, const Mint &rhs) {return lhs.x<rhs.x;}
};
template<>
ll Mint<0ll>::Mod=ll(1e18)+9;
using mint = Mint<MOD>;
using vm = vector<mint>;
int a[MX];
mint dp[MX][1002][3], tmp[MX][1002][3];
void solve() {
int n, l; cin >> n >> l;
rep(i, 1, n) cin >> a[i];
sort(a+1, a+n+1);
if (n==1) cout << 1 << nl, exit(0);
tmp[1][0][0] = tmp[1][0][1] = 1;
rep(i, 2, n) {
rep(j, 1, n) {
rep(k, 0, l) {
rep(l, 0, 2) {
int val = k + (2*j-l)*(a[i]-a[i-1]);
if (val > l) continue;
dp[j+1][val][l] += (j-l+1)*tmp[j][k][l];
dp[j][val][l] += (2*j-l)*tmp[j][k][l];
dp[j-1][val][l] += (j-1)*tmp[j][k][l];
if (l > 1) continue;
dp[j+1][val][l+1] += (1+l)*tmp[j][k][l];
dp[j][val][l+1] += (1+l)*tmp[j][k][l];
}
}
}
rep(j, 1, n) {
rep (k, 0, l) {
rep (l, 0, 2) {
tmp[j][k][l] = dp[j][k][l], dp[j][k][l] = 0;
}
}
}
}
mint ans = 0;
rep(i, 0, l) ans += tmp[1][i][2];
cout << ans << nl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) { solve(); }
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
