BZOJ 2849 和谐串

Link

Solution

显然可以暴力DP。对小范围打表找规律可以得结论。 然后套Wallis公式 \(\dfrac {(2n)!!}{(2n-1)!!}\sim \sqrt{\pi n}\) \(Ans\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;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利