算是一道比较好想的题 (?)
首先将 \(A\) 数组排序，从小到大插入 \(f\) 中，就可以脱掉绝对值符号。
设 $f_{i,j,s,t} $ 为插入前 \(i\) 小的数，在 \(f\) 数组中形成了 \(j\) 段，对整个柿子的贡献为 \(s\) ，且确定了 \(t\) 个边界（即不能在左边界的左边或右边界的右边再插入数字）的方案数。
当插入 \(A_i\) 时，若 \(A_j\) 与其相邻，那么就会有 \(A_i - A_j\) 的贡献。但是这样并不能方便的计算。
可以用 这道题 类似的技巧，将 \(A_i - A_j\) 变成 \(\sum\limits_{p = j + 1}^i A_p-A_{p - 1}\) ，于是就可以算出每个 \(A_i - A_j\) 对 \(s\) 的贡献了。
设 \(\Delta A = A_i - A_{i-1}\) ，每次插入 \(A_i\) 时，\(\Delta A\) 可以与 \((2j - t)\) 个小于 \(A_i\) 的数产生贡献。令 \(c = s + \Delta A \times (2j - t)\) ，那么有如下几种情况：
-
附原有的某一段中：因为附在这一段的左或右端点，但是有 \(t\) 个边界不能插数，所以可能插入的位置有 \((2j - t)\) 个。插入后段数和边界数不变，所以有 \(f_{i+1,j,c,t} = f_{i,j,s,t} \times (2j - t)\) 。
-
将某两段连成一段：只能插入到两段之间，所以可能插入的位置有 \((j-1)\) 个。插入后段数减一，边界数不变，所以 \(f_{i+1,j-1,c,t} = f_{i,j,s,t} \times (j - 1)\) 。
-
单独成段且不靠边界：只能插入在段与段或者段与边界之间，所以可能插入位置有 \((j + 1 - t)\) 个。插入后段数加一，边界数不变，所以 \(f_{i+1,j+1,s,t} = f_{i,j,s,t} \times (j + 1 - t)\) 。
-
单独成靠边界的一段：显然只有 \((2 - t)\) 个位置可以插入。插入后段数和边界数都加一，所以 \(f_{i+1,j+1,c,t+1} = f_{i,j,s,t} \times (2 - t)\) 。
-
将某一段连到边界上：显然也只有 \((2 - t)\) 个位置可以插入。插入后段数不变，边界数加一，所以 \(f_{i+1,j,c,t+1} = f_{i,j,s,t} \times (2 - t)\) 。
初始化 \(f_{0,0,0,0} = 1\) 。当 \(c > L\) 的时候就不必要转移了。
转移部分就写完了。最终答案就是 \(\sum\limits_{i=0}^L f_{n,1,i,2}\) 。时间复杂度 \(O(n^2 L)\)
注意 \(n = 1\) 时要特判输出 1 。
#include<cstdio>
#include<algorithm>
#define int long long
const int mod=1e9+7;
const int M=111,N=1111;
int f[M][M][N][3];
int n,l,a[M];
signed main(){
scanf("%lld%lld",&n,&l);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
if(n==1) return printf("1"),0;
std::sort(a+1,a+1+n);
f[0][0][0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
for(int s=0;s<=l;s++)
for(int t=0;t<=2;t++){
int c=(2*j-t)*(a[i+1]-a[i])+s;
if(c<=l){
(f[i+1][j+1][c][t]+=f[i][j][s][t]*(j+1-t)%mod)%=mod;
if(j>0){
(f[i+1][j][c][t]+=f[i][j][s][t]*(2*j-t)%mod)%=mod;
(f[i+1][j-1][c][t]+=f[i][j][s][t]*(j-1)%mod)%=mod;
if(t!=2) (f[i+1][j][c][t+1]+=f[i][j][s][t]*(2-t)%mod)%=mod;
}
if(t!=2) (f[i+1][j+1][c][t+1]+=f[i][j][s][t]*(2-t)%mod)%=mod;
}
}
int ans=0;
for(int i=0;i<=l;i++) (ans+=f[n][1][i][2])%=mod;
printf("%lld",ans);
return 0;
}