hihoCoder 1596 : Beautiful Sequence

Description

Consider a positive integer sequence a[1], ..., a[n] (n ≥ 3). If for every 2 ≤ i ≤ n-1, a[i-1] + a[i+1] ≥ 2 × a[i] holds, then we say this sequence is beautiful.

Now you have a positive integer sequence b[1], ..., b[n]. Please calculate the probability P that the resulting sequence is beautiful after uniformly random shuffling sequence b.

You're only required to output (P × (n!)) mod 1000000007. (Obviously P × (n!) is an integer)

Input

First line contains an integer n. (3 ≤ n ≤ 60)

Following n lines contain integers b[1], b[2], ..., b[n]. (1 ≤ b[i] ≤ 1000000000)

Output

Output (P × (n!)) mod 1000000007.

Sample Input

Sample Output

8
https://hihocoder.com/problemset/problem/1596dp鬼题
题目条件可化为a[i+1]-a[i]>=a[i]-a[i-1]
考虑排序再做分配
根据分析我们发现最后的高度序列是一个勾函数，先减小后增大
我们讨论b[i-1],b[i],b[i+1]的情况
显然i-1和i+1不可能同时大于i
只可能一个大于i一个小于，或两个都大于
但是两个都大于的情况显然只有一次，两边是不会有的
如5 3 5 1 3 5
那么就出现了两个都小于的情况
那么我们就可以dp
令f[i][j][k][l]表示最左边两个为i,j 最右边两个为k,l
我们先将最小值放入f[1][0][1][0]=1
接下来要放的数为max(i,k)+1,为什么？因为是排过序的，从小到大放就行了
判断是否满足：a[i+1]-a[i]>=a[i]-a[i-1]
还有一个细节：
当有多个最小值时，显然不能直接dp，以最小值数量为l=3举例
因为直接dp只能得到4种，而实际有6种(此题鬼处)
所以把所有最小值缩为一个，最后乘l!

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int Mod=;

 long long f[][][][],a[],p[],tmp,ans;

 int n;

 int main()

 {int i,j,k,l=;

     cin>>n;

     for (i=;i<=n;i++)

     {

         scanf("%lld",&a[i]);

     }

     sort(a+,a+n+);

     p[]=;

     for (i=;i<=n;i++)

     p[i]=(p[i-]*i)%Mod;

     for (i=;i<=n;i++)

     if (a[i]==a[]) l++;

     tmp=p[l];

     for (i=;i<=n-l+;i++)

     a[i]=a[i+l-];

     n=n-l+;

     f[][][][]=;

     for (i=;i<=n;i++)

     {

         for (j=;j<=n-;j++)

         {

             for (k=;k<=n;k++)

             {

                 for (l=;l<=n-;l++)

                 {

                     int z=max(i,k)+;

                     if (z==n+)

                     {

                         ans+=f[i][j][k][l];

                         ans%=Mod;

                         continue;

                     }

                     if (a[z]-a[k]>=a[k]-a[l]||l==)

                     f[i][j][z][k]+=f[i][j][k][l],f[i][j][z][k]%=Mod;

                     if (a[z]-a[i]>=a[i]-a[j]||j==)

                     f[z][i][k][l]+=f[i][j][k][l],f[z][i][k][l]%=Mod;

                 }

             }

         }

     }

     cout<<(ans*tmp)%Mod;

 }

巴特西

hihoCoder 1596 : Beautiful Sequence

Description

Input

Output

最新文章

热门文章