JZOJ 4345 Fountain

若确定了喷泉之间的相对位置，设 s=n∑i=2max(ri−1,ri)，则方案数为 (d−s+n−1n)。

考虑在此基础上 DP。
有个 max 并不好处理，考虑排序后逐一加入。
设 fi,j,k,l 表示从大到小考虑了 i 个喷泉，它们的间隙中有 j 个是可以插入新喷泉的，s=k，左右两端有 l=0/1/2 个可以插。

代码：

#include <cstdio>
#include <algorithm>
#include <functional>
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;
}