ZOJ Problem Set - 3822 Domination
Chieh
posted @ 2015年8月21日 21:30
in NO Answer No Speak
, 340 阅读
/* Author:Chieh Because Of Coding */ #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <queue> #include <vector> #define LL long long #define INF 1e9 #define EPS 1e-9 using namespace std; const int maxn=5*12; double ai[maxn*maxn][maxn][maxn]; int T,n,m; double ans; void init() { ans=0; scanf("%d%d",&n,&m); ai[0][0][0]=1; double p=n*m; for(int k=1; k<=n*m; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { ai[k][i][j]=0; ai[k][i][j]+=i*j*ai[k-1][i-1][j]/p; ai[k][i][j]+=j*i*ai[k-1][i][j-1]/p; ai[k][i][j]+=i*j*ai[k-1][i-1][j-1]/p; if((i!=n||j!=m)&&i*j>=k) { ai[k][i][j]+=ai[k-1][i][j]*(i*j-k+1)/p; } } } p--; } } void play() { double ans=0; for(int i=1; i<=n*m; i++) { ans+=ai[i][n][m]*i; } printf("%.10f\n",ans); } int main() { scanf("%d",&T); while(T--) { init(); play(); } return 0; }