/ ALGORITHM

Hihocoder 1596

Contest Information

source: It’s from the hihocoder

Description

给出一个正整数数列 $a[1], …, a[n](n>3) $,如果对于所有 $ 2 ≤ i ≤ n-1 $,都有 $ a[i-1] + a[i+1] ≥ 2×a[i] $,则称这个数列是美丽的。
现在有一个正整数数列 $b[1], …, b[n](n>3) $,可以任意调换元素位置,请问最多能生成多少个美丽数列,答案对 $10^9+7$ 取模。
数据范围:$ 3 ≤ n ≤ 60, 1 ≤ b[i] ≤ 1000000000 $

Input

4
1 2 1 3

Outpus

8

Solution

计算几个”美丽数列”,我们很容易发现它是一个凹数列,那么我们可以通过从中间往两边枚举来计算数列个数。

定义 $ DP[i][j][k][l][r] $ 为序列两端的元素序号为 $i, j, k ,l $ 时的方案总数:
当 $r=0$ 时,序列左端为 $i, j$,右端为 $k,l$;
当 $r=1$ 时,序列左端为 $j, k$,右端为 $l,i$;
转移时,判断一下是否满足条件就可以往两端添加了新元素 $i$ 了,最后答案为所有的 $DP[n][j][k][l][r]$ 。

AC code

int n,b[61];
map<int,int> M;
int f[61][61][61][61][2];
 
void solve()
{
    sort(b+1, b+1+n);
    f[1][1][1][1][0] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(b[i]==b[1])
        {
            memcpy(f[i], f[i-1], sizeof(f[0]));
            continue;
        }
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=n;l++)
                {
                    for(int r=0;r<2;r++)
                    {
                        if(!f[i-1][j][k][l][r]) continue;
                        int la,lb,rb,ra,x=f[i-1][j][k][l][r];
                        if(!r)
                            la = i-1, lb = j, rb = k, ra = l;
                        else
                            la = j, lb = k, rb = l, ra = i-1;
                        if(b[la]-b[i] <= b[lb]-b[la])
                            (f[i][la][rb][ra][0]+=x)%=mod;
                        if(b[ra]-b[rb]<= b[i]-b[ra])
                            (f[i][la][lb][ra][1]+=x)%=mod;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            for(int l=1;l<=n;l++)
                for(int r=0;r<2;r++)
                    (ans+=f[n][j][k][l][r])%=mod;
    int num = M[b[1]];
    for(int i=1;i<=num;i++)
        ans =  (LL)ans*i%mod;
    ans = (ans%mod+mod)%mod;
    out(ans);puts("");
}

int main()
{
    while(~scanf("%d", &n))
    {
        M.clear();CLR(f);
        for(int i=1;i<=n;i++) scanf("%d", &b[i]), M[b[i]]++;
        solve();
    }
}