题意：固定起点是0，给出一个序列表示n个点，所有点都在一条直线上，其中每个元素代表了从起点到这个点所走的距离。已知路过某个点不算到达这个点，则从起点出发，到达所有点的方案有许多种。求所有方案走的总路程/方案数，输出分子、分母，要求不含约数。
e.g:n=3 {2,3,5}，{2,3,5}{2,5,3}{3,2,5}{3,5,2}{5,2,3}{5,3,2}，总路程(5+7+7+8+9+8)=44，答案44/6=22/3，输出“22 3”。
分析：
1、以n=3序列{a1,a2,a3}为例，实际上是{0,a1,a2,a3}，起点确定，总共有n！中方案。
2、经过简单的思考就可以发现，每种方案的第一步比较特殊，因此分类讨论：
一、0->ak:这条线段会出现(n-1)!次，那么所有方案的第一步之和=(0->a1)*(n-1)!+(0->a2)*(n-1)!+(0->a3)*(n-1)!=(a1+a2+a3)*(n-1)!
二、ai->aj:既然是线段，在序列上必然是连续出现。形如ai->aj的线段会出现在第2步~第n步的任意一处位置，出现的次数为(n-2)!，所以ai->aj出现的总次数为(n-1)*(n-2)!=(n-1)!，那么所有方案的第2步~第n步之和=(a1->a2)*(n-1)!+(a2->a1)*(n-1)!+(a1->a3)*(n-1)!+(a3->a1)*(n-1)!+(a2->a3)*(n-1)!+(a3->a2)*(n-1)!=2*(|a1-a2|+|a1-a3|+|a2-a3|)*(n-1)!
3、“一”与“二”之和就是总路程，约掉(n-1)!后，答案就是：[(a1+...+an)+2*(∑|ai-aj|)]/n，(i!=j)
4、由于数据范围是105，直接枚举计算|ai-aj|会超时。
注意：计算|ai-aj|实际上就是计算序列{a1,a2,a3,a4}任意两条线段的长度之和。利用ai->aj覆盖了ai->a(j-1)，从左向右观察，则以a2结束的线段只有S1=a1->a2，以a3结束的线段有a1->a3,a2->a3，其中a1->a3可以看做a1->a2+a2->a3，这里a1->a2已经计算好了,所以S2=S1+2*(a2->a3)。同理，以a4结束的线段有a1->a4,a2->a4,a3->a4，不考虑a3->a4，其余的均是将以a3结束的线段延长a3->a4，所以S3=S2+3*(a3->a4)。
状态方程：Si=S(i-1)+i*|ai-a(i+1)|
注意：
1、long long T^T
2、给出的序列是乱序的
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std; const int MAXN=; int cmp(int a,int b)
{
return a<b;
} LL gcd(LL a,LL b)
{
if(a%b==)return b;
gcd(b,a%b);
} int a[MAXN]; int main()
{
LL n,cnt=;
scanf("%lld",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
cnt+=a[i];
}
a[]=;
sort(a,a+n+,cmp);
LL ans=,s=; for(int i=;i<n;i++)
{
s+=(a[i+]-a[i])*i;
ans+=s*;
} LL x=gcd(ans+cnt,n);
printf("%lld %lld\n",(ans+cnt)/x,n/x);
return ;
}