codeforces 340Ctourist Problem

C. Tourist Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
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.
Input
The first line contains integer n (2 ≤ n ≤ 105). Next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 107).
Output
Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.
Sample test(s)
input

3
2 3 5

output

22 3

Note
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  =  = .
제목의 대의: 아래의 데이터를 보면 제목의 뜻을 알 수 있다.길이를 모두 두 단점 사이의 거리로 바꿀 줄은 생각지도 못했다.그리고 법칙을 찾지만 0이 기점으로 확정되기 때문에 상황은 두 종류로 나뉜다.
아래의 대부분 문자는 Thousand Sunny에서 유래한 것으로 나는 약간의 변경을 했다.
1,n=3 서열 {a1,a2,a3}을 예로 들면 실제로는 {0,a1,a2,a3}이고 기점이 확정되어 모두 n이 있습니다!중안2. 간단한 사고를 통해 모든 방안의 첫 번째 단계가 비교적 특수하다는 것을 알 수 있기 때문에 분류 토론: 1, 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)! 2. ai->aj: 라인이니까 서열에 연속적으로 나타날 거야.아->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.'1'과'2'의 합은 총 노정이다. 약속(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,주어진 서열은 난서입니다
제목 주소: C. Tourist Problem
AC 코드:

#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
",sum/tmp,n/tmp);
    }
    return 0;
}