题意：有
n
n
个人进行了mm场比赛，告诉你了自己的每场排名，并且一场比赛中不会有并列，问最后自己的期望排名 题解：很明显期望
dp
d
p
，
dp[i][j]表示进行了i场比赛得分为j的期望人数
d
p
[
i
]
[
j
]
表
示
进
行
了
i
场
比
赛
得
分
为
j
的
期
望
人
数
那么转移就是
dp[i][j]=(∑j−1k=j−mdp[i][k]−dp[i][j−a[i]])/(m−1)
d
p
[
i
]
[
j
]
=
(
∑
k
=
j
−
m
j
−
1
d
p
[
i
]
[
k
]
−
d
p
[
i
]
[
j
−
a
[
i
]
]
)
/
(
m
−
1
)
对于每一个可能的状态，都有
1/(m−1)
1
/
(
m
−
1
)
的概率转移过来
初始化
dp[0][0]=m−1
d
p
[
0
]
[
0
]
=
m
−
1
这里简单的维护一个前缀和就可以，然后貌似
n∗n∗m
n
∗
n
∗
m
这题数组正好开的下，不过使用滚动数组更好就是了
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#define LL long long
#define mod 1000000007
using namespace std;
const int maxn =
500000 +
5;
const LL INF =
1e18 +
5;
int a[maxn];
double dp[
2][
100*
1000 +
5];
double sum[
2][
100*
1000+
5];
int main(){
int n,m;
int tot =
0;
scanf(
"%d%d",&n,&m);
for(
int i=
1; i<=n; i++){
scanf(
"%d",&a[i]);
tot += a[i];
}
dp[
0][
0] = m-
1;
for(
int j=
0; j<=n*m; j++)
sum[
0][j] = m-
1;
for(
int i=
1; i<=n; i++){
memset(dp[i%
2],
0,
sizeof(dp[i%
2]));
memset(sum[i%
2],
0,
sizeof(sum[i%
2]));
for(
int j=i; j<=i*m; j++){
int top = j-
1;
int bottom = max(
0,j-m);
if(bottom ==
0)
dp[i%
2][j] = sum[(i-
1)%
2][top];
else
dp[i%
2][j] = sum[(i-
1)%
2][top] - sum[(i-
1)%
2][bottom-
1];
if(bottom <= j-a[i] && j-a[i] <= top)
dp[i%
2][j] -= dp[(i-
1)%
2][j-a[i]];
dp[i%
2][j] /= m-
1;
}
for(
int j=i; j<=i*m+m; j++){
sum[i%
2][j] = sum[i%
2][j-
1] + dp[i%
2][j];
}
}
double ans =
0;
for(
int i=
0; i<tot; i++){
ans += dp[n%
2][i];
}
printf(
"%.12lf\n",ans+
1);
}
