【BZOJ4832】抵制克苏恩（矩阵快速幂，动态规划）

题面

题解

#include<iostream>

#include<cstdio>

using namespace std;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int m,K,n;

int bh[9][9][9],tot,lim[5];

double P[6][170][170];

double tmp[170],Ans[170];

void dfs(int a,int b,int c)

{

	if(a>lim[1]||b>lim[2]||c>lim[3])return;

	if(bh[a][b][c]||a+b+c>K)return;

	bh[a][b][c]=++tot;

	dfs(a+1,b,c);dfs(a,b+1,c);dfs(a,b,c+1);

}

void Plus(int &A,int &B,int &C){if(m==1)++A;if(m==2)++B;if(m==3)++C;}

void pre()

{

	for(int a=0;a<=K&&a<=lim[1];++a)

		for(int b=0;a+b<=K&&b<=lim[2];++b)

			for(int c=0;a+b+c<=K&&c<=lim[3];++c)

			{

				int s=a+b+c+1,p=bh[a][b][c];

				P[0][p][tot+1]+=1.0/s;P[0][p][p]+=1.0/s;

				if(a)P[0][p][bh[a-1][b][c]]+=1.0*a/s;

				if(b)

				{

					int A=a+1,B=b-1,C=c;if(s<=K)Plus(A,B,C);

					P[0][p][bh[A][B][C]]+=1.0*b/s;

				}

				if(c)

				{

					int A=a,B=b+1,C=c-1;if(s<=K)Plus(A,B,C);

					P[0][p][bh[A][B][C]]+=1.0*c/s;

				}

			}

	P[0][tot+1][tot+1]+=1;

	for(int p=1;p<=5;++p)

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

			for(int k=1;k<=tot+1;++k)

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

					P[p][i][j]+=P[p-1][i][k]*P[p-1][k][j];

}

int main()

{

	int T=read();m=3;K=7;

	for(int i=1;i<=m;++i)lim[i]=K;

	dfs(0,0,0);pre();

	while(T--)

	{

		n=read();int A=read(),B=read(),C=read(),p=0;

		for(int i=1;i<=tot+1;++i)Ans[i]=0;Ans[bh[A][B][C]]=1;

		while(n)

		{

			if(n&1)

			{

				for(int i=1;i<=tot+1;++i)tmp[i]=Ans[i],Ans[i]=0;

				for(int k=1;k<=tot+1;++k)

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

						Ans[j]+=tmp[k]*P[p][k][j];

			}

			++p;n>>=1;

		}

		printf("%.2lf\n",Ans[tot+1]);

	}

	return 0;

}

巴特西

【BZOJ4832】抵制克苏恩（矩阵快速幂，动态规划）

【BZOJ4832】抵制克苏恩（矩阵快速幂，动态规划）

题面

题解

最新文章

热门文章