codeforces 340C Tourist Problem（简单数学题）

题意：固定起点是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=111111;

int cmp(int a,int b)
{

return a<b;
}

LL gcd(LL a,LL b)
{

if(a%b==0)return b;

gcd(b,a%b);
}

int a[MAXN];

int main()
{

LL n,cnt=0;

scanf("%lld",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

cnt+=a[i];

}

a[0]=0;

sort(a,a+n+1,cmp);

LL ans=0,s=0;


for(int i=1;i<n;i++)

{

s+=(a[i+1]-a[i])*i;

ans+=s*2;

}


LL x=gcd(ans+cnt,n);

printf("%lld %lldn",(ans+cnt)/x,n/x);

return 0;
}