做题时间：2026.8.8 题目难度：普及+/提高- | 题目链接 | 洛谷链接

这次的 E 很简单但是做出 E 的好像没有 F 多，而且我整场比赛基本都在调 E。

这题首先题面就很难懂，我一开始还读错了。

题意其实是抽牌是完全随机的但是 Takahashi 会记住他翻开过的所有牌在哪个位置，这才是本题的关键。

先说一个结论，本题的所有 $a_i$ 的唯一作用就是用来求平均数。因为对于每一种移除牌的集合，总会有一种相对应的集合。所以我们只需要记录最终移除了几张牌。很明显移除每张牌的期望得分为所有牌的平均数。

那基本就做出来了。我们先定义 Takahashi 记住的牌为“手牌”，很明显每种“手牌”最多 $1$ 张；所有“手牌”对应的没有被记住的为“明牌”；剩下的叫“暗牌”。

定义 dp[i][j][k] 为场上还有 $2i$ 张没有被移除，Takahashi 还有 $j$ 点血量，并且他有 $k$ 张“手牌”。

很明显 Takahashi 肯定会先去翻不是“手牌”的牌，则：

• 如果翻到了“明牌”，那么 Takahashi 肯定会继续翻这张牌对应的“手牌”。“手牌”数量减一，得分加一，场上剩余牌减一，也就是继承 dp[i-1][j][k-1]。

• 如果翻到了“暗牌”，那么继续随机翻。

  1. 翻到了“明牌”：很明显血量减一，“手牌”数量加一。但是这也意味着下回合可以直接打出一组“手牌”和“明牌”将得分加一。那么场上剩余牌减一，手牌数量不变，得分加一，血量减一，即继承 dp[i-1][j-1][k]。

  2. 翻到了数值相同的“暗牌”：直接场上剩余牌减一，得分加一就行。继承 dp[i-1][j][k]。

  3. 翻到了数值不相同的暗牌：这运气就不好了，血量减一且不得分。但是这也就意味着“手牌”会多两张，所以继承 dp[i][j-1][k+2]。

好了，思路讲完了，对应概率自己手算就行。但是接下来才是重点，可以省去 $40$ 分钟的调试时间。

首先，无论如何，你的 $k$ 是永远不能大于 $i$ 的，这个在整个代码都要仔细检查。而且你的数组不能越界（即 $i,j,k$ 不能小于 $0$）。

剩下的写代码就行，基本不会出错（除非你把概率算错了）。

#include<bits/stdc++.h>
using namespace std;
const int N=210;
double dp[N][N][N],a[N];
signed main()
{
	int n,m;cin>>n>>m;double sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];sum/=n;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=i;k++)
	{
		if(k>0)dp[i][j][k]+=(dp[i-1][j][k-1]+1)*(1.0*k/(2*i-k));
		//抽到一个明牌，自动选择另一个
		if(k>0&&i!=k&&j!=1)dp[i][j][k]+=(dp[i-1][j-1][k]+1)*(1.0*(2*i-2*k)/(2*i-k)*k/(2*i-k-1));
		//先抽暗牌再抽明牌，下回合自动选两个明牌
		if(k!=i)dp[i][j][k]+=(dp[i-1][j][k]+1)*(1.0*(2*i-2*k)/(2*i-k)*1/(2*i-k-1));
		//抽到两个相等的暗牌
		if(k<=i-2)dp[i][j][k]+=dp[i][j-1][k+2]*(1.0*(2*i-2*k)/(2*i-k)*(2*i-2*k-2)/(2*i-k-1));
		//抽到两个不相等的暗牌
	}
	printf("%.10lf",dp[n][m][0]*sum);
	return 0;
}