【搬自TC_SRM583 Hard】【JZOJ4844】抗拒黄泉 题解

题目大意

  有一个 $n \times m$ 的棋盘，每个格子要么是 0 要么是 1。每天等概率地选择一个 1 格子进行标记，若某时刻每行、每列都至少有一个格子被标记，则结束。求结束的期望天数。
  $n,m \le 20,\ \ n \times m \le 200$

【50%】n,m<=8

  设 $f[s1][s2]$ 表示行状态为 $s1$、列状态为 $s2$，到达结束的期望天数。
  设总的 1 格子数量为 $tot$，那么对于当前状态，有 $t[s1][s2]$ 个 1 格子你选它不会改变当前状态，剩余 $tot-t[s1][s2]$ 个 1 格子则会改变当前状态。
  则 $f[s1][s2]=\frac{t[s1][s2]}{tot}(f[s1][s2]+1)+\sum\frac{1}{tot}(f[s1'][s2']+1)$，移一下项就解出来了。

【100%】n,m<=20, n*m<=200

  设 $F(i)$ 表示经过 $i$ 次操作结束的概率，$P(i)$ 表示经过 $i$ 次操作仍未结束的概率，则

$$\begin{array}{rcl} ans&=&\sum_{i=1}^\infty F(i)×i\\ &=&\sum_{i=0}^\infty(P(i)-P(i+1))×(i+1)\\ &=&\sum_{i=0}^\infty P(i) \end{array}$$

  考虑如何计算 $P(i)$。既然未结束，则一定是漏掉了一些行或列。漏掉的意思是那些行和那些列所包含的 1 格子永远选不到。设行列状态为 $S$，设选中该状态包含的 1 格子的概率为 $p(S)$（这个是小写），则容斥一下可得到

$$P(i)=\sum_{|S|是奇数}(1-p(S))^i-\sum_{|S|是偶数}(1-p(S))^i$$

  所以

$$ans=\sum_{i=0}^\infty \sum_{|S|是奇数}(1-p(S))^i-\sum_{|S|是偶数}(1-p(S))^i$$

  等比数列公式一下可得

$$ans=\sum_{|S|是奇数}\frac{1}{p(S)}-\sum_{|S|是偶数}\frac{1}{p(S)}$$

  设总的 1 格子数量为 $tot$，$S$包含的 1 格子数量为 $t[S]$，则

$$ans=\sum_{|S|是奇数}\frac{tot}{t(S)}-\sum_{|S|是偶数}\frac{tot}{t(S)}$$

  设使 $t[S]=X$ 的状态 $S$ 数量为 $num[X]$（这里的数量是指容斥后的数量，即奇数减偶数），则

$$ans=\sum_{X=1}^{tot}num[X]×\frac{tot}{X}$$

  求 $num[X]$ 则是一个简单状压dp，不赘述。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#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;

typedef long long LL;

const int maxn=25, maxN=2e4+5;

int n,m,N,mp[maxn][maxn],er[maxn],b0;

int w[maxN];
int get(int x)
{
    int re=0;
    for(; x; x-=(x&(-x))) re++;
    return re;
}

int Sb[maxn],bl[maxn],br[maxn];
LL f[205][2],num[205];
int main()
{
    fo(i,1,20) er[i]=1<<(i-1);

    scanf("%d %d",&n,&m);
    fo(i,1,n)
        fo(j,1,m) scanf("%d",&mp[i][j]);
    if (n>m) //n、m必有一个<=14，为了方便下面的状压dp，把小的作为行
    {
        fo(i,1,n)
            fo(j,(i<=m)?i:1,m) swap(mp[i][j],mp[j][i]);
        swap(n,m);
    }
    N=(1<<n)-1;

    fo(j,1,m)
    {
        Sb[j]=Sb[j-1];
        fo(i,1,n) if (mp[i][j])
        {
            bl[j]+=er[i];
            br[i]++;
            Sb[j]++;
            b0++;
        }
    }
    fo(s,0,N) w[s]=get(s);

    fo(s,0,N)
    {
        int st=0;
        fo(i,1,n) if (s&er[i])
        {
            if (!br[i]) {st=-1; break;}
            st+=br[i];
        }
        if (st==-1) continue;
        memset(f,0,sizeof(f));
        f[st][0]=1;
        fo(j,1,m) if (Sb[j]-Sb[j-1])
            fd(i,min(st+Sb[j],b0),st)
            {
                LL g[2]={f[i][0],f[i][1]};
                f[i][0]=f[i][1]=0;
                fo(k,0,1)
                {
                    f[i][k]+=g[k];
                    if (i+get(bl[j]-(s&bl[j]))<=b0)
                        f[i+w[bl[j]-(s&bl[j])]][k^1]+=g[k];
                }
            }
        fo(i,st,b0)
        {
            fo(k,0,1) if ((get(s)^k)&1) num[i]+=f[i][k]; else num[i]-=f[i][k];
        }
    }

    long double ans=0;
    fo(x,1,b0) ans+=num[x]*(long double)b0/x;

    printf("%.5f\n",(double)ans);
}