UVA557 Burger
题目大意
称一个长度为 \(n\) 的01串是好的，当且仅当 \(0\) 和 \(1\) 在该串中分别出现恰好 \(\frac n2\) 次，且该串的最后两位相同。
现给定 \(n\)（\(n\) 为偶数），求 该串是好的 的概率。
Solve
正难则反，考虑求出最后两位不同的概率。
令 \(m=\frac n2\)，那么条件“最后两位不同”等价于前 \(2m-2\) 位中，有 \(m-1\) 个 \(0\) 和 \(1\)。
显然该串满足此条件的概率是：
\[P_n=\frac{{2m-2}\choose{m-1}}{2^{2m-2}}=\frac{{n-2}\choose{\frac n2-1}}{2^{n-2}} \]即从前 \(2m-2\) 位中选出 \(m-1\) 位令其为 \(0\) 的方案数除以总方案数。而每一位上是 \(0\) 或 \(1\) 有两种选择，所以共有 \(2^{2m-2}\) 种方案。
所以最后的答案就是 \(1-P\) 了。
然后考虑怎么求组合数，显然不能利用递推求，时间和空间上都过不去，而用阶乘和逆元的话，我不会。
考虑手推个递推式，因为我们发现只需求 \(2i\choose i\)，显然不难推。
\[\begin{align} {2i\choose i}&=\frac{(2i)!}{i!\times i!}=\frac{2i\times(2i-1)\times\dots\times(i+1)}{i!}\\ \\\\ {2i+2\choose i+1}&=\frac{(2i+2)!}{(i+1)!\times (i+1)!}\\ &=\frac{(2i+2)\times(2i+1)\times\dots\times(i+2)}{(i+1)!}\\ &=(2i+2)\times(2i+1)\times\frac{2i\times(2i-1)\times\dots\times(i+1)}{(i+1)\times(i+1)!}\\ &=(2i+2)\times(2i+1)\times\frac{{2i\choose i}\times i!}{(i+1)\times(i+1)!}\\ &=2\times(2i+1)\times\frac{2i\choose i}{i+1}\quad ((2i+2)约掉(i+2)剩2，i!约掉(i+1)!剩(i+1))\\ 即:\\ {2i\choose i}&=2\times(2i-1)\times\frac{2i-2\choose i-1}{i}\\ 即:\\ {i\choose \frac i2}&=2\times(i-1)\times\frac{i-2\choose \frac i2-1}{\frac i2}=4\times(i-1)\times\frac{i-2\choose \frac i2-1}i\\\\ 将{i-2\choose \frac i2-1}代入得P_i&=\frac{{i-2}\choose{\frac i2-1}}{2^{i-2}}\\ 将{i\choose \frac i2}代入得P_{i+2}=\frac{i\choose \frac i2}{2^i}&=4\times(i-1)\times\frac{i-2\choose \frac i2-1}i\div2^i\\ &=4\times(i-1)\times\frac{i-2\choose \frac i2-1}{2^i}\div i\\ &=(i-1)\times\frac{i-2\choose \frac i2-1}{2^{i-2}}\div i\\ &=P_i\times(i-1)\div i\\ 即:\\ P_i&=P_{i-2}\times(i-1)\div i \end{align} \]代码就很简单了。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1,2,3,"Ofast","inline")
using namespace std;
#define int long long
inline int read()
{
short f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int t,n,mi,m;
double ans[100010]={1}/*C(i/2,i)*/;
signed main()
{
for(int i=2;i<=100000;i+=2)
ans[i]=ans[i-2]*(i-1)/i;
t=read();
for(int i=1;i<=t;i=-~i)
printf("%.4lf\n",1-ans[read()-2]);
return 0;
}