题意：给你一个N×M的棋盘，每一次随机在这里放一个子（不能重复）问你最后每一行每一列只要有一个子的期望次数
解题思路：dp[i][j][s] 已经用 i 个子 占了 j 行 s 列的概率，再找出状态转移方程就行。
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月18日 星期六 10时19分16秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 double dp[3000][52][52]; 28 int n, m; 29 double solve(int x,int y,int z) 30 { 31 32 } 33 void print() 34 { 35 for(int i = 1;i <= n*m ;i ++) 36 { 37 for(int j = 1; j <= n+1;j ++) 38 { 39 for(int s = 1; s<= m+1; s ++) 40 { printf("%lf ",dp[i][j][s]); 41 } 42 printf(" "); 43 } 44 printf(" "); 45 } 46 47 } 48 int main(){ 49 int t; 50 scanf("%d",&t); 51 while(t--) 52 { 53 scanf("%d %d",&n,&m); 54 if(n > m ) 55 swap(n,m); 56 memset(dp,0,sizeof(dp)); 57 dp[1][1][1] = 1.0 ; 58 for(int i = 2;i <= n*m ;i ++) 59 { 60 for(int j = 1; j <= n;j ++) 61 { 62 for(int s = 1; s<= m; s ++) 63 { 64 int k = (n*m-(i-1)); 65 if(!(j == n && s ==m)) 66 dp[i][j][s] += dp[i-1][j][s]*(max(0,j*s-(i-1))*1.0/k); 67 dp[i][j][s+1] += dp[i-1][j][s] *(max(0,j*m-s*j)*1.0/k); 68 dp[i][j+1][s] += dp[i-1][j][s] *(max(0,s*n-s*j)*1.0/k); 69 dp[i][j+1][s+1] += dp[i-1][j][s] *((n*m-(s*n+j*m-s*j))*1.0/k); 70 } 71 } 72 } 73 //print(); 74 double ans = 0.0 ; 75 for(int i = 1;i <= n*m ;i ++) 76 ans += i * dp[i][n][m]; 77 printf("%.10lf ",ans); 78 } 79 return 0; 80 }