学步园

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4655

题目大意：给你一个序列ai，每个点可以涂ai种颜色，颜色一样的算同一块，ai可以任意排列，问你所有方案的块数和最大为多少？

思路：直接来解题报告吧

如果不考虑相邻块的重复，那么总数就为n*S（S为TTai），现在考虑相邻两个ai的重复，就要剪掉，依次考虑过去，如果ai和a（i+1）相同，那么就要剪掉min（ai，a（i+1））*S/（ai*a（i+1）） ，也就是题解里的S/max（ai，a（i+1）），然后全部都SIMGA起来就可以了，注意这里减得时候不用再乘n了，一种涂色方案只代表n*S总数里多算的一种，相邻的两块颜色一样只是这种颜色涂法的块数少了1而已。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef __int64 lld;

const int MOD = 1e9 +7 ;

const int MAXN = 1111111 ;

int a[MAXN],b[MAXN];

lld left[MAXN],right[MAXN];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i = 1,tot =0;tot<=n;i++)
        {
            b[++tot] = a[i];
            if(i>=(n-i+1)) break;
            b[++tot] = a[n-i+1];
        }
        /*for(int i = 1;i<=n;i++)
            printf("%d ",b[i]);
        puts("");*/
        left[0] = 1;
        for(int i = 1;i<=n;i++)
        {
            left[i] = (left[i-1]*b[i])%MOD;
        }
        right[n+1] = 1;
        for(int i = n;i>=1;i--)
            right[i] = (right[i+1] * b[i])%MOD;
        lld A = (n*left[n])%MOD;
        lld B = 0 ;
        for(int i = 1;i<n;i++)
        {
            B = (B + ((left[i-1]*right[i+2])%MOD*min(b[i],b[i+1]))%MOD)%MOD;
        }
        printf("%I64d\n",(A-B+MOD)%MOD);
    }
    return 0;
}