旅行者问题
【问题描述】
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
【Solution】
虽然A了但还是很想吐槽，这题竟然是个数学问题...
首先先枚举每条可能的第一条路。对于某一种可能的第一条路，其余点的排列方式有(n-1)!种，所以这条路对所有以这条路为起点的路径的贡献和为(n-1)*dist[i]。
对于某一条路i--j，其余(n-2)个点的排列方式有(n-2)种，而这条路可以插入的位置有n-1种，所以这条路对所有带这条路的路径的贡献和为(n-2)!*(n-1)*abs(dist[i]-dist[j])=(n-1)!*abs(dist[i]-dist[j])。
根据以上两种情况，路径和=
现在的问题就是怎么求加号后面的那一坨了。
我们将dist从大到小排序，排序后忽略的情况在最后求出路径和乘二即可。用S[i]表示到i的所有路程和。我们发现：
S2 = dist[1] - dist[2]
S3 = dist[1] - dist[3] + dist[2] - dist[3] = (dist[1] - dist[2] + dist[2] - a3) + dist[2] - dist[3] = S2 + 2 *（dist[2] - dist[3]）
S4 = dist[1] - dist[4] + dist[2] - dist[4] + dist[3] - dist[4] = (dist[1] - dist[3] + dist[3] - dist[4]) + (dist[2] - dist[3] + dist[3] - dist[4]) + (dist[3] - dist[4]) = S3 + 3 * (dist[3] - dist[4])
不难看出，S[i]可以由递推求出，递推式为S[i]=S[i-1]+(i-1)*(dist[i-1]-dist[i])。虽然式子里还要乘个(n-1)!，但是由于分子为n!，约一下分母上的(n-1)!消掉了，分子变成n，求个gcd分子分母一除输出答案就行了。
AC代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int N;
int dist[];
long long sum,ans;
long long recs[];
void input(){
scanf("%d",&N);
for(int i=;i<=N;++i) scanf("%d",&dist[i]);
}
int cmp(const int a,const int b){
return a>b;
}
long long gcd(long long x,int y){
long long ys=;
while(ys!=){
ys=x%y;
x=y;
y=ys;
}
return x;
}
int main(){
input();
for(int i=;i<=N;++i) sum+=dist[i];
sort(dist+,dist++N,cmp); recs[]=dist[]-dist[];
for(int i=;i<=N;++i)
recs[i]=recs[i-]+(i-)*(dist[i-]-dist[i]);
for(int i=;i<=N;++i) ans+=recs[i];
ans=ans*+sum;
long long k=gcd(ans,N);
printf("%I64d %I64d",ans/k,N/k);
return ;
}