某考试 T1 fair (18.5.1版)

转化一下模型：每天可以选1也可以选0，但是任意前i天(i<=n)1的个数都必须>=0的个数，求总方案数/2^n。

然后可以发现这是一个经典题，随便推一下公式发现等于 C(n,n/2)/2^n [请在二维平面直角坐标系上自行演算，（x,y）可以到 (x+1,y)和(x,y+1)，横坐标代表1的个数，纵坐标代表0的个数，求不经过 y=x+1 这条直线的路径总数 (终点是任意 (x,y) 满足 x+y==n 且 x>=y)]

本来以为卡卡常数就过去了23333，没想到竟然还要用阶乘逼近公式！

那就记一下好啦，反正这玩意也根本没法理解啊qwq

当n很大的时候，n! 与 sqrt(2*π*n) * (n/e)^n 之间的相对误差非常小(然鹅？)，所以可以近似成相等啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#define ll long long

#define D double

using namespace std;

const D pi=acos(-1),E=exp(1);

D now=1,ans=1,B=log(4);

int n,hf;

inline void solve(){

	hf=n>>1;

	if(n&1){ ans=n/(D)(n-hf)/2,n--;}

	ans=log(ans);

	for(int i=hf+1;i<=n;i++) ans+=log(i)-log(i-hf)-B;

	ans=exp(ans);

}

inline D jc(int x){ return log(sqrt(2*pi*x))+x*log(x/E);}

inline void Sim(){

	ans=jc(n)-jc(n>>1)-jc(n-(n>>1))-log(2)*n;

	ans=exp(ans);

}

int main(){

	freopen("fair.in","r",stdin);

	freopen("fair.out","w",stdout);

	cin>>n;

	if(n<=1e6) solve();

	else Sim();

	printf("%.11lf\n",ans);

	return 0;

}

巴特西

某考试 T1 fair (18.5.1版)

最新文章

热门文章