HDU4655題意+分析

哎這題有點意思。。

一開始腫麼看都不理解題意，發現好多ACM題都這樣，好多英文意思不能完全理解，只得照樣例猜啦，猜不出來？？ 那就靠神隊友解釋了，囧。

就是排列，塗色使結果最大化。

反正別人的博客把這題的題意解釋的很清楚了，我這只小牛就把自己的拙思路稍提一下。

也許做題多了馬上就能感覺出這題當 a1,an,a2,an-1這樣排列順序效果會最大化，囧。

關鍵是代碼實現的過程也很坎坷，自己一開始以為前面的減少的部分可能會與後面減少的部分有沖突，其實不然，還是自己沒深入分析，，，

那這樣就用總的情況減掉會有“沖突”的情況就行了。

除法取模，根本木有。。

要不就求逆元，可實際上不用，遞推一下就OK了。

還有又順便復習了一下取模過程中可能出現的溢出情況。。

#include <cstdio>   
#include <cstring>   
#include <algorithm>   
#include <vector>   
using namespace std;  
//除法取模顯然有錯誤啊，都可能出來0了。。。   
typedef __int64 LL;  
LL a[1000005];  
LL b[1000005];  
LL sum1[1000005];  
LL sum2[1000005];  
LL min(LL a,LL b)  
{  
    if(a>b) return b;  
    else return a;  
}  
const int maxn=1000000007;  
int main()  
{  
    int case_num;  
    scanf("%d",&case_num);  
    while(case_num--)  
    {  
        int n;  
        scanf("%d",&n);  
        for(int i=1;i<=n;i++)  
            scanf("%I64d",&a[i]);  
        sort(a+1,a+1+n);  
        int temp1=1,temp2=n;  
        for(int i=1;i<=n;i+=2)  
            b[i]=a[temp1++];  
        for(int i=2;i<=n;i+=2)  
            b[i]=a[temp2--];  
        sum1[0]=1;  
        sum1[1]=b[1];  
        sum2[n]=b[n];  
        sum2[n+1]=1;  
        for(int i=2;i<=n;i++)  
        {  
            sum1[i]=sum1[i-1]*b[i]%maxn;  
        }  
        for(int i=n-1;i>=1;i--)  
        {  
            sum2[i]=sum2[i+1]*b[i]%maxn;  
        }  
        long long ans=(sum1[n]%maxn)*(n%maxn)%maxn;  
        long long temp=0;  
        for(int i=2;i<=n;i++)  
        {  
            temp=(temp%maxn+(((min(b[i],b[i-1])*sum1[i-2])%maxn)*(sum2[i+1]%maxn))%maxn)%maxn;  
        }  
        ans=(ans-temp+maxn)%maxn;  
        printf("%lld\n",ans);  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//除法取模顯然有錯誤啊，都可能出來0了。。。
typedef __int64 LL;
LL a[1000005];
LL b[1000005];
LL sum1[1000005];
LL sum2[1000005];
LL min(LL a,LL b)
{
    if(a>b) return b;
    else return a;
}
const int maxn=1000000007;
int main()
{
    int case_num;
    scanf("%d",&case_num);
    while(case_num--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%I64d",&a[i]);
        sort(a+1,a+1+n);
        int temp1=1,temp2=n;
        for(int i=1;i<=n;i+=2)
            b[i]=a[temp1++];
        for(int i=2;i<=n;i+=2)
            b[i]=a[temp2--];
        sum1[0]=1;
        sum1[1]=b[1];
        sum2[n]=b[n];
        sum2[n+1]=1;
        for(int i=2;i<=n;i++)
        {
            sum1[i]=sum1[i-1]*b[i]%maxn;
        }
        for(int i=n-1;i>=1;i--)
        {
            sum2[i]=sum2[i+1]*b[i]%maxn;
        }
        long long ans=(sum1[n]%maxn)*(n%maxn)%maxn;
        long long temp=0;
        for(int i=2;i<=n;i++)
        {
            temp=(temp%maxn+(((min(b[i],b[i-1])*sum1[i-2])%maxn)*(sum2[i+1]%maxn))%maxn)%maxn;
        }
        ans=(ans-temp+maxn)%maxn;
        printf("%lld\n",ans);
    }
    return 0;
}