题解 P5750 钉子和小球
我们来看一下这道题：
如果所有钉子都还在，那么
小球落在第
p_i = \frac{C_n^i}{2^n} = \frac{ n! }{ 2^n i! (n-i)! }
其实这道题是一个dp，我们发现
我们设一个个的小格子中的概率为
因为我们要求的为一个最简分数，所以
f[i][j].a 表示分子，f[i][j].b 表示分子，这是个既约分数
我们可以发现
落在这个位置的小球概率为1，所以
f[0][1].a=1,f[0][1].b=1
我们通过观察法可以得到，如果在f[i][j] 的正下方
有
钉子，那么
f[i][j] 有 \frac{1}{2} 的概率落在 f[i+1][j] 上，
有 \frac{1}{2} 的概率落在 f[i+1][j+1] 上
但是如果我们拔掉一个钉子
f[0][1] 就只有可能落在f[2][2] 上面，所以我们得到
如果在f[i][j] 的正下方
没有
钉子，那么
f[i][j] 落在 f[i+2][j+1] 上
所以dp方程就出来了，初始值为
f[0][1].a=1,f[0][1].b=1
若c[i][j]==0 则f[i+1][j+1]+=f[i-1][j]
如果有不理解的地方可以私信我！
下面是代码时间！！！
注意，要写一个分数类出来（就是重载一下运算符代码里面有解释）！
#include<bits/stdc++.h>
using namespace std;
int read()
{
char c;
int w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
int ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
long long gcd(long long a,long long b)//欧几里得算法
{
return b==0?a:gcd(b,a%b);
}
struct node
{
long long a,b;
void huajian()//让该分数成为既约分数
{
long long w=gcd(a,b);
a=a/w;
b/=w;
}
node operator /(const long long y)const//一个分数除以一个整数
{
node t = *this;
t.b *= y,t.huajian();
return t;
}
node operator +(node y)const//一个分数加上另外一个分数
{
if(a==0)
{
y.huajian();
return y;
}
node o=*this;
if(y.a==0)
{
o.huajian();
return o;
}
long long p=gcd(o.b,y.b);
o.a*=(y.b/p);o.a+=y.a*(o.b/p);o.b*=(y.b/p);
o.huajian();
return o;
}
}f[1005][1005];//其实只要开50就够了！
int n,m;
int c[1005][1005];
int main(){
n=read();
m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
char w;
while((w=getchar())!='*'&&w!='.');
if(w=='*')c[i][j]=1;
}
}
f[0][1].a=1;//初始化
f[0][1].b=1;
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=n+1;j++)
{
f[i][j].b=1;//注意要吧所有分数初始化一下，不然除以0化简时会RE
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(c[i][j])
{
node p=f[i-1][j];//有钉子的时候
p=p/2;
f[i][j]=f[i][j]+p;
f[i][j+1]=f[i][j+1]+p;
}
else
{
f[i+1][j+1]=f[i+1][j+1]+f[i-1][j];//没有钉子的时候
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i+1;j++)
{
f[i][j].huajian();//记得要化简哟！！！
}
f[n][m+1].huajian();
cout<<f[n][m+1].a<<"/"<<f[n][m+1].b<<endl;//cout大发好
return 0;
}