题目大意：给你$D$个格子，有$n$个喷水器，每个喷水器有一个喷水距离$r_i$。
现在你需要在这$D$个格子中选择$n$个位置按照任意顺序安装这$n$个喷水器，需要满足$n$个喷水器互相喷不到对方。
问方案数，对$10^9+7$取模
数据范围：$n$,$r_i≤40$，$D≤10^5$
我们不妨考虑我们钦定了这$n$个喷水器的出现顺序，从左到右第$i$个喷水器编号为$p[i]$。
确定排列顺序后，令$d=\sum \limits_{i=1}^{n-1} max(r_{p[i]},r_{p[i+1]})$
我们发现上式累加的实际上是相邻两个喷水器之间的最小间隔
我们尝试把这个间隔中的格子看成是一个格子。
我们就可以把原序列中$D$个格子看成是$D-d-1$个了。
现在也就是变成了要在这剩下的格子之间插入这$n$个喷水器，方案数显然为$\binom{D-d-1+n}{n}$。
下面考虑如何求不同的排列顺序数量。
我们先将$n$个喷水器按照喷水半径进行排序。
设$f[i][j][k]$表示前i个喷水器必须出现，且这$i$个喷水器间（包括两端），有$j$个可以插入喷水器，且由这些喷水器累加出的$d$为$k$的方案数量。
下面考虑在$f[i][j][k]$的基础上插入第$i+1$个喷水器。
假定这个喷水器插入后，两侧不能再插入喷水器，则有$f[i+1][j-1][k+2r_{i+1}]+=f[i][j][k]\times (j-2)$
假定这个喷水器插入后，只有一侧能插入喷水器，则有$f[i+1][j][k+r_{i+1}]+=f[i][j][k]\times (2j-2)$
上面两个转移需要$-2$的原因显然（并不能允许最左侧和最右侧插入喷水器）
假定这个喷水器插入后，两侧皆可以插入喷水器，则有$f[i+1][j+1][k]+=f[i][j][k]\times j$
初始情况：$f[1][2][0]=1$，答案为$\sum \limits_{i=1}^{\infty} f[n][2][i]$
转移和答案统计的时候记得取模即可
时间复杂度：$O(n^2\sum \limits_{i=1}^{n} r_i)$
#include<bits/stdc++.h>
#define M 42
#define N 110000
#define L long long
#define MOD 1000000007
using namespace std; L pow_mod(L x,L k){L ans=; for(;k;k>>=,x=x*x%MOD) if(k&) ans=ans*x%MOD; return ans;}
L fac[N]={},invfac[N]={};
L C(int n,int m){if(n-m<) return ; return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;} int n,D,r[M]={};
L f[M][M][M*M]={}; int main(){
fac[]=; for(int i=;i<N;i++) fac[i]=fac[i-]*i%MOD;
invfac[N-]=pow_mod(fac[N-],MOD-);
for(int i=N-;~i;i--) invfac[i]=invfac[i+]*(i+)%MOD; scanf("%d%d",&n,&D);
for(int i=;i<=n;i++) scanf("%d",r+i);
sort(r+,r+n+);
f[][][]=;
for(int i=;i<n;i++)
for(int j=;j<=n+;j++)
for(int k=;k<M*M;k++)
if(f[i][j][k]){
(f[i+][j+][k]+=f[i][j][k]*j)%=MOD;
if(j>) (f[i+][j-][k+*r[i+]]+=f[i][j][k]*(j-))%=MOD;
if(j>) (f[i+][j][k+r[i+]]+=f[i][j][k]*(*j-))%=MOD;
}
L ans=;
for(int d=;d<M*M;d++)
if(f[n][][d]){
(ans+=C(D-d-+n,n)*f[n][][d])%=MOD;
}
cout<<ans<<endl;
}