#include <bits/stdc++.h>
using namespace std;
const int maxn = 101, maxl = 2000, mod = 1e9 + 7;
int dp[maxn][maxn][3][3][maxl], a[maxn];
int main()
{
int n, l;
cin >> n >> l;
for (int i = 1;i <= n;i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
long long int ans = 0;
do
{
int ret = 0;
for (int i = 1;i < n;i++)
{
ret += abs(a[i] - a[i + 1]);
}
if (ret <= l)
{
ans++;
}
}while (next_permutation(a + 1, a + n + 1));
cout << ans;
return 0;
dp[0][0][0][0][0] = 1;
for (int i = 0;i <= n;i++)
{
for (int j = 0;j <= n;j++)
{
for (int noe = 0;noe < 2;noe++)
{
for (int nos = 0;nos < 2;nos++)
{
for (int c = 0;c <= l;c++)
{
long long int p = dp[i][j][nos][noe][c];
int cc = c + (2 * j - nos - noe) * (a[i + 1] - a[i]);
if (p == 0 or cc > l or i == n)
{
continue;
}
dp[i + 1][j][nos][noe][cc] += p * (j - noe) % mod;
dp[i + 1][j][nos][noe][cc] %= mod;
dp[i + 1][j][nos][noe][cc] += p * (j - nos) % mod;
dp[i + 1][j][nos][noe][cc] %= mod;
dp[i + 1][j + 1][nos][noe][cc] += p;
dp[i + 1][j + 1][nos][noe][cc] %= mod;
if (j > 1)
{
dp[i + 1][j - 1][nos][noe][cc] += p * ((j - noe - nos) * (j - nos - 1) + nos * (j - nos - noe)) % mod;
if (i == n - 1)
{
dp[i + 1][j - 1][nos][noe][cc] += p * nos * noe;
}
dp[i + 1][j - 1][nos][noe][cc] %= mod;
}
if (nos == 0)
{
dp[i + 1][j + 1][nos + 1][noe][cc] += p;
dp[i + 1][j + 1][nos + 1][noe][cc] %= mod;
dp[i + 1][j][nos + 1][noe][cc] += p * (j - noe) % mod;
if (i == n - 1)
{
dp[i + 1][j][nos + 1][noe][cc] += p * noe;
}
dp[i + 1][j][nos + 1][noe][cc] %= mod;
}
if (noe == 0)
{
dp[i + 1][j][nos][noe + 1][cc] += p * (j - nos) % mod;
if (i == n - 1)
{
dp[i + 1][j][nos][noe + 1][cc] += p * nos;
}
dp[i + 1][j][nos][noe + 1][cc] %= mod;
dp[i + 1][j + 1][nos][noe + 1][cc] += p;
dp[i + 1][j + 1][nos][noe + 1][cc] %= mod;
}
}
}
}
}
}
for (int i = 0;i <= l;i++)
{
ans += dp[n][1][1][1][i];
ans %= mod;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |