威海外贸网站建设电话,丽水市莲都建设分局网站,wordpress個人網站域名,ac86u做网站服务器题目描述 给你一个\(n\times m\)的棋盘#xff0c;每次随机在棋盘上放一个国际象棋中的车#xff0c;不能和以前放的重叠。每个车可以控制当前行和当前列。当所有行和所有列都被控制时结束游戏。问你结束时期望放了多少个车。 注意#xff1a;结束的条件是所有行和所有列都被…题目描述 给你一个\(n\times m\)的棋盘每次随机在棋盘上放一个国际象棋中的车不能和以前放的重叠。每个车可以控制当前行和当前列。当所有行和所有列都被控制时结束游戏。问你结束时期望放了多少个车。 注意结束的条件是所有行和所有列都被控制而不是所有格子都被控制。 \(n,m\leq 50\) 题解 简单DP \(f_{i,j,k}\)表示放了\(k\)个车后控制了\(i\)行\(j\)列的概率\[ f_{i,j,k}\frac{f_{i,j,k-1}\times(ij-(k-1))f_{i,j-1,k-1}\times i(m-j1)f_{i-1,j,k-1}\times j(n-i1)f_{i-1,j-1,k-1}\times(n-i1)(m-j1)}{nm-k1} \] 答案是\[ \sum_{i1}^{nm}i(f_{n,m,i}-f_{n,m,i-1}) \] 弄个滚动数组搞一下 时间复杂度\(O(n^4)\) 代码 #includecstdio
#includecstring
#includealgorithm
#includecstdlib
#includectime
#includeutility
using namespace std;
typedef long long ll;
typedef pairint,int pii;
double f[2][60][60];
void solve()
{double ans0;int n,m;scanf(%d%d,n,m);memset(f,0,sizeof f);int i,j,k;f[0][0][0]1;int t0;for(k1;kn*m;k){t^1;double now1./(n*m-k1);memset(f[t],0,sizeof f[t]);for(i1;in;i)for(j1;jm;j)f[t][i][j](f[t^1][i][j]*(i*j-k1)f[t^1][i-1][j]*(n-i1)*jf[t^1][i][j-1]*i*(m-j1)f[t^1][i-1][j-1]*(n-i1)*(m-j1))*now;ansk*(f[t][n][m]-f[t^1][n][m]);}printf(%.10lf\n,ans);
}
int main()
{int t;scanf(%d,t);while(t--)solve();return 0;
} 转载于:https://www.cnblogs.com/ywwyww/p/8511350.html
