若确定了喷泉之间的相对位置，设 \(s = \sum\limits_{i=2}^n \max(r_{i-1},r_i)\)，则方案数为 \(\binom{d-s+n-1}n\)。
考虑在此基础上 DP。
有个 \(\max\) 并不好处理，考虑排序后逐一加入。
设 \(f_{i,j,k,l}\) 表示从大到小考虑了 \(i\) 个喷泉，它们的间隙中有 \(j\) 个是可以插入新喷泉的，\(s = k\)，左右两端有 \(l = 0/1/2\) 个可以插。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
const int N = 40;
const int D = 1e5 + 40;
const int S = 1600;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int n,d;
int a[N + 5];
int f[N + 5][N + 5][S + 5][3];
int fac[D + 5],ifac[D + 5],ans;
inline int C(int n,int m)
{
return (long long)fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
inline void trans(int &s,int v)
{
s = (s + v) % mod;
}
int main()
{
scanf("%d%d",&n,&d),fac[0] = 1;
for(register int i = 1;i <= D;++i)
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[D] = fpow(fac[D],mod - 2);
for(register int i = D;i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
sort(a + 1,a + n + 1,greater<int>());
if(n == 1)
{
printf("%d\n",d);
return 0;
}
if(n == 2)
{
printf("%d\n",2 * C(d - a[1] + 1,2) % mod);
return 0;
}
f[1][0][a[1] * 2][2] = 1,f[1][0][a[1]][1] = 2;
for(register int i = 1,v;i < n;++i)
for(register int j = 0;j <= n;++j)
for(register int k = 0;k <= S;++k)
for(register int l = 0;l <= 2;++l)
if(f[i][j][k][l])
{
v = f[i][j][k][l];
trans(f[i + 1][j + 1][k + 2 * a[i + 1]][l],(long long)v * (j + l) % mod);
trans(f[i + 1][j][k + a[i + 1]][l],v * (2LL * j + l) % mod);
j && (trans(f[i + 1][j - 1][k][l],(long long)v * j % mod),1);
l && (
trans(f[i + 1][j + 1][k + a[i + 1]][l - 1],(long long)v * l % mod),
trans(f[i + 1][j][k][l - 1],(long long)v * l % mod),1);
}
for(register int i = 0;i <= S;++i)
ans = (ans + (long long)f[n][0][i][0] * C(d - i + n - 1,n)) % mod;
printf("%d\n",ans);
return 0;
}