[sgu 508] 逆概率

给定n个球，它们要么黑，要么白。一开始不知道里面有几个是黑的，但是黑球的数目是等概率分布的。然后等概率地取里面的a+b个球，结果发现其中有a个白球，b个黑球。然后要求出原来有i(i = 1..n)个黑球的概率。

zYc说用xxxx公式……反正没听懂，然后比赛时很脑残地不会搞。
后来自己想了一下，其实可以看成一共有$$C_n^{a + b} * (n + 1)$$种等概率的情况。前面的组合数是就是这a+b个球的取法，后面的n+1是黑球的数目。
然后既然结果是(a, b)，那么就分别算出$$C_n^{a + b} * (n + 1)$$种情况下，一共有多少种是符合(a, b)的，记为sum。然后有i个黑球的概率就是看有i个黑球时，可以对(a, b)造成多少个等概率事件的“贡献”，最后除以sum就得解。
现在看起来好像很简单的样子。
真正的勇士要敢于直面自己当时是SB这样血淋淋的事实……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 55;
int n, a, b, p;
lld C[N][N];
double u[N];

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	scanf("%d%d%d%d", &n, &a, &b, &p);
	if (p == 0) {
		puts("0 0");
		return 0;
	}
	C[0][0] = 1;
	for (int i = 1; i <= 50; i++) {
		for (int j = 0; j <= i; j++) {
			C[i][j] = (j ? C[i - 1][j - 1] : 0) + C[i - 1][j];
		}
	}
	lld sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += C[i][a] * C[n - i][b];
	}
	for (int i = 0; i <= n; i++) {
		u[i] = C[i][a] * C[n - i][b] / (double)sum;
//		printf("%d %.12lf\n", i, u[i]);
	}
	int bi = -1, bj = -1;
	for (int i = 0; i <= n; i++) {
		double ret = 0;
		for (int j = i; j <= n; j++) {
			ret += u[j];
			if (ret + 1e-14 >= p / 100.0) {
				if (bi == -1 || j - i < bj - bi) {
					bi = i;
					bj = j;
				}
			}
		}
	}
	printf("%d %d\n", bi, bj);
}

[sgu 508] 逆概率

加入对话

留下评论

取消回复