BZOJ 2849 和谐串

发表于 | 更新于

Link

Solution

显然可以暴力DP。对小范围打表找规律可以得结论。 然后套Wallis公式 (2n)!!(2n−1)!!∼πn\dfrac {(2n)!!}{(2n-1)!!}\sim \sqrt{\pi n} Ans≈πn2n+1Ans\approx\dfrac {\sqrt{\pi n}}{2n+1}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "lucida"
const int N=1e7,MAXN=N+11;
const double pi=acos(-1);
double Ans[MAXN];
void Prep() {
	Ans[0]=1;
	for(int i=1;i<=N;++i) {
		Ans[i]=Ans[i-1]/(2*i+1)*2*i;
	}
}
double Calc(int64 n) {
	if(n<=N) {
		return Ans[n];
	} else {
		return sqrt(pi*n)/(2*n+1); 
	}
}
int main() {
//	freopen("input","r",stdin);
	os.precision(20);
	Prep();
	int T;is>>T;
	while(T--) {
		int64 n;is>>n;
		os<<Calc(n)<<'\n';
	}
	return 0;
}