1 second
256 megabytes
standard input
standard output
Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants
to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequencea1, a2,
..., an. The
number ak represents
that the kth destination is at distance ak kilometers
from the starting point. No two destinations are located in the same place.
Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer
0, as he stops his trip at the last destination.
The distance between destination located at kilometer x and next destination, located at kilometer y,
is |x - y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as
he visits all n destinations and he doesn't visit a destination more than once.
Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he
asks you to help him.
The first line contains integer n (2 ≤ n ≤ 105).
Next line contains n distinct integers a1, a2,
..., an (1 ≤ ai ≤ 107).
Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.
3 2 3 5
22 3
Consider 6 possible routes:
- [2, 3, 5]: total distance traveled: |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.
The average travel distance is 
= 
= 
.
2、经过简单的思考就可以发现，每种方案的第一步比较特殊，因此分类讨论：
一、0->ak:这条线段会出现
(n-1)!次，由于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)!，然后采取0到最后一个没取的an之间插空，共有i-1种。所以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<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
__int64 gcd(__int64 m,__int64 n)
{
__int64 tmp;
while(n)
{
tmp=m%n;
m=n;
n=tmp;
}
return m;
}
int main()
{
int n,i;
__int64 sum,sum1,sum2;
while(~scanf("%d",&n))
{
sum=sum1=sum2=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum1+=a[i];
}
sort(a,a+n+1);
__int64 tmp=0;
for(i=1;i<n;i++)
{
tmp+=(a[i+1]-a[i])*i;
sum2+=tmp<<1;
}
//sum1第一类的和,sum2第二类的和
sum=sum1+sum2;
tmp=gcd(sum,n);
printf("%I64d %I64d\n",sum/tmp,n/tmp);
}
return 0;
}