Description
大概是说(m)个人参加(n)场比赛，每场一人有一个排名，每场没有两个人排名相同，一个人最后的得分是(n)场比赛的排名相加，现在已知其中一个人（叫做(A)好了）(n)场比赛的排名，求最后按照得分降序排列后，这个人的期望排名
Solution
这题一开始有点无从下手（流下蒟蒻的泪水）
那。。冷静分析一波，首先我们要求的答案应该是：总分(<=)自己得分（记为(score)好了）的期望人数+1
然后因为除去(A)这个人，其他的(m-1)个人的情况是相同的，期望人数可以由：概率*(m-1)来得到
那所以我们现在就只考虑一个人（剩下的(m-1)个人中的一个），要求这个人总分(<=score)的概率
我们记(f[i][j])表示这个人经过(i)场比赛之后，总分为(j)的概率，那么我们可以得到转移式子：
这里的(rank[i])表示的是(A)在第(i)场比赛中的排名，这个转移的具体意义就是枚举这个人在第(i)场的排名，然后上界为(min(m,j))是因为只有(m)个人，(k!=rank[i])是因为没有两个人在同一场排名相同，所以这个人的排名不能是(A)在这场的排名
具体怎么求的话，我们可以把这个东西写成一个前缀和的形式，我们多开一个数组(sum[i][j]=sumlimits_{k=0}^{j-1}f[i][j])，特别的所有的(sum[i][0]=0)
然后前缀和一下再把(f[i][rank[i]])减掉就好了，最后的答案就是(sum[n][score]*(m-1)+1)
空间比较大所以可以考虑滚动数组，然后如果我没用long double的话。。好像会爆精度qwq可能是因为写挫了qwq（以及因为某种奇怪的原因cf上面好像。。直接printf一个long double会出锅qwq）
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,MX=100010;
long double p[2][MX],sum[2][MX];//sum[x]=sum_{i=0}{x-1} p[i]
int rk[N];
int n,m,score;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
score=0;
for (int i=1;i<=n;++i) scanf("%d",rk+i),score+=rk[i];
int pre=0,now=1,l,r;
p[0][0]=1;
for (int i=1;i<=n*m;++i) sum[0][i]=1;
if (m==1){printf("%d
",1);return 0;}
for (int i=1;i<=n;++i){
memset(p[now],0,sizeof(p[now]));
sum[now][0]=0; sum[now][1]=0;
for (int j=1;j<=n*m+1;++j){
l=max(0,j-m),r=j;
p[now][j]+=(sum[pre][r]-sum[pre][l])/(1.0*(m-1));
if (j-rk[i]>=0)
p[now][j]-=p[pre][j-rk[i]]/(1.0*(m-1));
sum[now][j+1]=sum[now][j]+p[now][j];
}
swap(now,pre);
}
printf("%.15Lf
",sum[pre][score]*(m-1)+1.0);
}