一、寫在前面
這題似乎是一道原創題目（不是博主原創），所以并不能在任何OJ上評測，博主在網盤上上傳了數據（網盤地址：http://pan.baidu.com/s/1mibdMXi），諸位看官需者自取。另外博主使用此題并沒有獲得出題人授權，如果出題人看到這篇blog并認為在下侵犯了您的權利，請用站內消息與在下聯系，在下會立即刪除這篇blog，給您帶來的困擾之處敬請諒解。
博主上傳這道題主要是因為這題牽扯許多數學運算，推導過程比較復雜，但是卻沒有用到任何算法或者數學定理，可以說這是一道想法題的典范。本篇blog中介紹的方法為博主原創，轉載請標明出處。
二、題目
題目描述
lahub是一個旅行者的粉絲，他想成為一個真正的旅行者，所以他計劃開始一段旅行。lahub想去參觀n個目的地（都在一條直道上）。lahub在起點開始他的旅行。第i個目的地和起點的距離為ai千米（ai為非負整數）。不存在兩個目的地和起點的距離相同。
從第i個目的地走到第j個目的地所走的路程為 |ai-aj|千米。我們把參觀n個目的地的順序稱作一次“旅行”。lahub可以參觀他想要參觀的任意順序，但是每個目的地有且只能被參觀一次（參觀順序為n的排列）。
lahub把所有可能的“旅行”都寫在一張紙上，并且記下每個“旅行”所要走的路程。他對所有“旅行”的路程之和的平均值感興趣。但是他覺得計算太枯燥了，所以就向你尋求幫助。
輸入
第一行一個正整數n。
第二行n個非負整數a1,a2,....,an（1≤ai≤10^7）。
輸出
兩個整數，答案用最簡分數形式輸出，第一個為分子，第二個為分母。
樣例輸入
3
2 3 5
樣例輸出
22 3
樣例提示
樣例有6種可能的旅行：
[2, 3, 5]: |2 – 0| + |3 – 2| + |5 – 3| = 5;
[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.
答案為 1/6 * （5+7+7+8+9+8）=44/6=22/3
數據范圍
30% n<=10
50% n<=1000
100% n<=100000
三、題目分析
首先，我們不妨拋開題目背景，將題目大致翻譯成一個數學題：
給出一個正整數n，并給出a1、a2……an共n個互不相同的正整數。對于序列an的每一種排列ax1、ax2……axn，令Sx=|ax1-0|+|ax2-ax1|+……+|axn-axn-1|，求S的平均數。
由于題目明確說明，當i≠j時，不存在ai=aj的情況。那么，排列的總情況數就為n的全排列即n!種。
為了便于講解，我們規定序列an嚴格升序（代碼實現時只需要做一次sort處理）
通過對S的定義我們不難發現，若不考慮ai作為axn的情況，對于每個i，在每個求S的算式中，ai都會作為被減數和減數各出現一次。此外，由于當i=xn時，ai在算式中不作為減數出現，并且對于每個i，i=xn的情況各有(n-1)!種，所以對于每個i，ai總共作為被減數出現n!次，作為減數出現[n!-(n-1)!]次。
我們先討論ai作為被減數出現的情況：
當ai作為被減數時，0和其余n-1個數都可以作為ai的減數，且他們成為ai的減數的機會是均等的（ai雨露均沾？？）所以含0在內的n個數各會作為ai的減數(n-1)!次。設aj為ai的減數，那么當且僅當j<i時，|ai-aj|去絕對值符號后會得到ai-aj；反之，當且僅當j>i時，|ai-aj|去絕對值符號后會得到aj-ai。由于當i合法時，0總比ai小，所以我們可以得到有i個數使ai去絕對值符號之后帶正號，n-i個數使ai去絕對值符號后帶負號。
以上，我們整理后得到：ai作為被減數時對ΣS的影響為：
同理，我們討論ai作為減數出現的情況：
當ai作為減數時，其余n-1個數都可以作為ai的被減數，且他們成為ai的被減數的機會是均等的（ai雨露均沾+1）所以其余n-1個數各會作為ai的減數(n-1)!次（想一想，為什么）。設aj為ai的被減數，那么同上，當且僅當j<i時，|aj-ai|去絕對值符號后會得到ai-aj；反之，當且僅當j>i時，|aj-ai|去絕對值符號后會得到aj-ai。所以我們可以得到有i-1個數使ai去絕對值符號之后帶正號，n-i個數使ai去絕對值符號后帶負號。
以上，我們整理后得到：ai作為減數時對ΣS的影響為：
綜合以上兩種情況，我們得到：ai對ΣS的影響為：
最后，我們只需要將每個ai對ΣS的影響結合起來，便得到了答案：
注意：1、記得將答案化簡為最簡分數后輸出（分子、分母各除以其最大公約數）；
2、不開long long見祖宗，十年OI一場空。
四、代碼實現
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=100010; 5 long long a[MAXN]; 6 long long gcd(long long x,int n) 7 { 8 long long xx=x,yy=n; 9 while(yy) 10 { 11 long long t=xx%yy; 12 xx=yy; 13 yy=t; 14 } 15 return xx; 16 } 17 int main() 18 { 19 freopen("tourist.in","r",stdin); 20 freopen("tourist.out","w",stdout); 21 int n; 22 long long x=0; 23 scanf("%d",&n); 24 int i; 25 for(i=1;i<=n;++i) 26 scanf("%d",&a[i]); 27 sort(a+1,a+1+n); 28 for(i=1;i<=n;++i) 29 x=x+a[i]*(4*i-2*n-1); 30 long long g=gcd(x,n); 31 printf("%lld ",x/g); 32 printf("%d\n",n/g); 33 fclose(stdin); 34 fclose(stdout); 35 return 0; 36 }
弱弱地說一句，本蒟蒻碼字也不容易，轉載請注明出處http://www.cnblogs.com/Maki-Nishikino/p/5994679.html
