Topcoder SRM583

题目大意

有一个n*m的01矩阵，每次等概率的选择一个1，然后将其标记（可能将已经标记的再标记），求每一行与每一列都至少有一个被标记的期望次数。
$n\times m \le 200$

O($2^{n+m}$nm)做法

设f[r][c]表示当前局面为行的二进制状态是r列的二进制状态是c的期望,g[r][c]类似的，表示其概率。
考虑转移，枚举一个当前行或列没有其他点被标记的点，然后转移式应当是这样的：
$\sum_{i=1}^{+∞}(f[r][c]+g[r][c]*i)\times \frac{1}{tot}\times(\frac{sum(r,c)}{tot})^{i-1}$
（其中sum(r,c)表示r,c局面下被覆盖的点的个数）
$=f[r][c]\times\frac1{tot-sum(r,c)}+g[r][c]\times \frac{tot}{(tot-sum(r,c))^2}$
于是可以顺推，g类似

正解

我们的答案可以写成一个这样的形式：
$Ans=\sum_{i=1}^{+∞}F[i]*i$
F[i]表示刚好随机i次后将所有行和列覆盖的概率
同时可以发现
$Ans=\sum_{i=0}^{+∞}P[i]$
P[i]表示做了i次后还没有成功的概率
于是可以容斥

然后极限化一下，就可以得到这种形式：

于是可以枚举行状态，然后利用DP解决。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;int get(){char ch;int s=0;bool bz=0;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-')bz=1;else s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';if (bz)return -s;return s;
}const int N = 210;typedef double db;int f[N][2][N];
int a[N][N];
int n,m,tot;
bool bz[N];
int num[N];void calc(){memset(f,0,sizeof(f));f[0][0][0]=1;int tmp=0;fo(i,1,m){int v=0;fo(j,1,n)if (a[j][i]&&!bz[j])v++;fo(j,0,1)fo(k,0,tmp){f[i][j][k]+=f[i-1][j][k];f[i][j^1][k+v]+=f[i-1][j][k];}tmp+=v;}int pd=0;fo(i,1,n)pd^=bz[i];int v=0;fo(i,1,n)if (bz[i]){fo(j,1,m)if (a[i][j])v++;}fo(j,0,1)fo(k,0,tmp)num[k+v]+=int((pd^j)*2-1)*f[m][j][k];
}void dfs(int x){if (x>n){calc();return;}bz[x]=0;dfs(x+1);bz[x]=1;dfs(x+1);
}int main(){freopen("refuse.in","r",stdin);freopen("refuse.out","w",stdout);n=get();m=get();tot=0;if (n<m)fo(i,1,n)fo(j,1,m)tot+=(a[i][j]=get());else{fo(j,1,n)fo(i,1,m)tot+=(a[i][j]=get());swap(n,m);}dfs(1);db ans=0;fo(i,1,tot)ans+=db(num[i])*tot/i;printf("%.5lf\n",ans);fclose(stdin);fclose(stdout);return 0;
}