//khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 1e2 + 10;
const int xm = 1e3 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
int n, a[xn], L, dp[xn][xn][2][2][xm], ans;
int main(){
fast_io;
cin >> n >> L;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 0; i < 2; ++ i)
for (int j = 0; j < 2; ++ j)
dp[1][1][i][j][0] = 1;
for (int i = 1; i < n; ++ i){
for (int j = 1; j <= i; ++ j){
for (int f1 = 0; f1 < 2; ++ f1){
for (int f2 = 0; f2 < 2; ++ f2){
for (int k = 0; k <= L; ++ k){
int kp = k + (j + j - 2 + f1 + f2) * (a[i + 1] - a[i]);
if (L < kp)
continue;
dp[i + 1][j][f1][f2][kp] = (dp[i + 1][j][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j + j - 2) % mod) % mod;
dp[i + 1][j + 1][f1][f2][kp] = (dp[i + 1][j + 1][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j - 1) % mod) % mod;
dp[i + 1][j - 1][f1][f2][kp] = (dp[i + 1][j - 1][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j - 1) % mod) % mod;
if (f1){
for (int f3 = 0; f3 < 2; ++ f3){
dp[i + 1][j][f3][f2][kp] = (dp[i + 1][j][f3][f2][kp] + dp[i][j][f1][f2][k]) % mod;
dp[i + 1][j + 1][f3][f2][kp] = (dp[i + 1][j + 1][f3][f2][kp] + dp[i][j][f1][f2][k]) % mod;
}
}
if (f2){
for (int f3 = 0; f3 < 2; ++ f3){
dp[i + 1][j][f1][f3][kp] = (dp[i + 1][j][f1][f3][kp] + dp[i][j][f1][f2][k]) % mod;
dp[i + 1][j + 1][f1][f3][kp] = (dp[i + 1][j + 1][f1][f3][kp] + dp[i][j][f1][f2][k]) % mod;
}
}
}
}
}
}
}
for (int i = 0; i <= L; ++ i)
ans = (ans + dp[n][1][0][0][i]) % mod;
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
844 KB |
Output is correct |
| 6 |
Correct |
2 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
844 KB |
Output is correct |
| 8 |
Correct |
1 ms |
960 KB |
Output is correct |
| 9 |
Correct |
2 ms |
844 KB |
Output is correct |
| 10 |
Correct |
1 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1980 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
844 KB |
Output is correct |
| 6 |
Correct |
2 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
844 KB |
Output is correct |
| 8 |
Correct |
1 ms |
960 KB |
Output is correct |
| 9 |
Correct |
2 ms |
844 KB |
Output is correct |
| 10 |
Correct |
1 ms |
972 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1980 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 21 |
Correct |
8 ms |
10828 KB |
Output is correct |
| 22 |
Correct |
198 ms |
50520 KB |
Output is correct |
| 23 |
Correct |
249 ms |
66552 KB |
Output is correct |
| 24 |
Correct |
232 ms |
73288 KB |
Output is correct |
| 25 |
Correct |
252 ms |
65812 KB |
Output is correct |
| 26 |
Correct |
224 ms |
67636 KB |
Output is correct |
| 27 |
Correct |
116 ms |
81916 KB |
Output is correct |
| 28 |
Correct |
135 ms |
82008 KB |
Output is correct |
| 29 |
Correct |
215 ms |
81416 KB |
Output is correct |
| 30 |
Correct |
250 ms |
66024 KB |
Output is correct |
