bzoj 1867: [Noi1999]钉子和小球【dp】

设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好

主要是要手写分数比较麻烦

#include<iostream>

#include<cstdio>

using namespace std;

const int N=55;

int n,m;

char a[N][N];

long long gcd(long long a,long long b)

{

	return !b?a:gcd(b,a%b);

}

struct fs

{

	long long x,y;

	fs(long long X=0,long long Y=1)

	{

		x=X,y=Y;

	}

	fs operator + (const fs &a) const

	{

		long long d=gcd(a.y,y),l=a.y/d*y;

		fs b=fs(l/y*x+l/a.y*a.x,l);

		long long g=gcd(b.x,b.y);

		return fs(b.x/g,b.y/g);

	}

	fs operator * (const fs &a) const

	{

		fs b=fs(x*a.x,y*a.y);

		long long g=gcd(b.x,b.y);

		return fs(b.x/g,b.y/g);

	}

}f[N][N];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=i;j++)

		{

			a[i][j]=getchar();

			while(a[i][j]!='*'&&a[i][j]!='.')

				a[i][j]=getchar();

		}

	f[1][1]=fs(1,1);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=i;j++)

		{

			if(a[i][j]=='*')

			{

				f[i+1][j]=f[i+1][j]+f[i][j]*fs(1,2);

				f[i+1][j+1]=f[i+1][j+1]+f[i][j]*fs(1,2);

			}

			else

				f[i+2][j+1]=f[i+2][j+1]+f[i][j];

		}

	printf("%lld/%lld\n",f[n+1][m+1].x,f[n+1][m+1].y);

	return 0;

}

/*

5 2

*

*.

***

*.**

*****

*/

巴特西

bzoj 1867: [Noi1999]钉子和小球【dp】

最新文章

热门文章