[LightOJ]Beating the Dataset（组合数学）

题目传送门：Beating the Dataset | LightOJ

题目大意 / Problem

有一个ACM选手在刷题，这题答案多组"YES" or "NO"，给定了数据组数和答案字节数（可以算出ye和no各有多少个），每一个数据提交后会返回正确答案并作为下一次的提交，问错误数据个数的期望。

思路 / Thought

别想复杂了。其实很简单。

首先算出X和Y，分别表示YES和NO的数目。

一共有N组数据，那么期望可以这么算 E = 错误组数 / 总组数，每一对"0 1"或者“1 0”肯定有且仅有第一个是错误的，特殊地当第一个输出为0时也是错的。

换句话说，就是这个选手的输出会形成一个01串，求这个01串的某个位置与前一个位置的数字不同或第一个数为0的期望。

现在假设每个数字1 0都是不同的，那么总方法数为(X + Y)!，要求01连在一起的方法数，那么就把01捆绑起来当做一个数字，和剩下的数字一起全排列，方法数为X * (X + Y - 1)!，为什么要乘X * Y呢？因为我们假设每个数字都是互异的，那么选出这样一个01数字的方法就有X * Y种。那么10也一样，另外一种情况是选出一个0放到首位方法数为Y。所以期望为：

代码 / Code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int kase = 1;
void solve()
{
	int N, M;cin >> N >> M;
	int X = M - 2 * N, Y = N - c1; // X 为 yes 的数目， Y为 no 的数目 
	printf("Case %lld: %.7lf\n", kase ++, (2.0 * X * Y + Y) / N);
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();
	return 0;
}