Water 题解

· · 题解

显然这道题可以分成两个部分来计算，总方案数和所有方案的时间总数。

先考虑总方案数：

对于同一连通块，如果没有分支（任意位置放水都会使这一层全填满，如下图），很显然其方案数就是深度 +1（可以不放）。

如果有分支，因为任意分支的方案不会互相影响，所以根据乘法原理不同分支的方案数直接乘起来即可，比如下图的方案数就应该是 10。

显然是否有分支可以用并查集来维护，记 f_i 表示 i 所对应连通块的方案数，当两个分支合并时，显然大的连通块方案数即 f_x \times f_y +1。

由于水因重力会下沉，所以很自然的就应该从下往上处理。对于每一层先将同层的连通块合并，再考虑从下一层更新过来。

若果发现相邻两点在该层是连通块但下一层和该点未连通，则可认为下层是一个新的分支，将其方案数乘到当前连通块。

在和下一层合并完后，还需再加上将水放在该层的一种方案。

对于最终仍未不连通的连通块，其方案之间仍是互不干扰的则需全部乘起来。

时间复杂度为 O(n^2)。

到此方案数就求完了，下面考虑求总时间。

考虑求出每种时间的方案数，最后在乘上时间。

记每个点的深度为这个点到其所在的连通块中最靠近顶部的点的距离。

对于同一连通块，该块所需时间为该方案下所有水中最浅的水的深度。

而对于不同连通块，最终时间即为所有连通块中时间的最大值。

显然，对于某一深度求出答案并不是很容易，考虑容斥，如果已知前缀和，那么直接相减即为每一深度的答案。

那么如何来求前缀和，由于最终各块之间是取最大值，故只需知道各块之间方案的前缀和，相乘即可。

现在问题转化为求各连通块各深度方案数的前缀和。

类比求总方案数，由于总方案数是从下往上求的，故 f_i 就表示该连通块深度大于等于目前深度的方案数，

但考虑对于每个最终连通块，在每个深度可能有多个分支，需要将每个分支的深度都乘起来（可以对于每个连通块开一个 \tt{vector}，每个 \tt{vector} 的大小为该块最大深度 +1）。

现在就得到了每个连通块的后缀和，前缀和只需用总和减去后缀和。

这个问题就解决了。

但万恶的出题人卡了空间有如下几种解决方式：

  2. 把只有一层的连通块忽略，这样连通块的个数最多为 \dfrac{n^2}{4}。

  3. 并查集数组可以循环使用。

  4. 在预处理每个点的深度时用 \tt{bfs} 并且对于每一行中连续的一段点只入队一次。

综上：时间复杂度为 O(n^2)、空间复杂度为 O(n^2)。

const int N=5001,mod=998244353;
int n,m,ans1=1,cnt,sum[N],ans2,mul[N],mx,dep,fir[N*N/4],Tm[N*N/2],id[N*N],f[N<<1],fa[N<<1];
queue<int>q;
bool s[N][N];
#define get_id(x,y) (m*(x-1)+y)
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline int bfs(int &i,int &j,int ct)
{
    int t=1,h=0,x=i,y=j,k,kk,*id_,*id__,dep_=ct,l,r,mx=0;
    q.push(i),Tm[0]=j;
    for(r=y,id_=id+get_id(i,j);s[x][r];++id_,++r)*id_=dep_;
    for(l=y,id_=id+get_id(i,j);s[x][l];--id_,--l)*id_=dep_;
    for(;h!=t;h++)
    {
        x=q.front(),q.pop(),y=Tm[h],mx=max(mx,x-i),dep_=ct+x-i;
        for(r=y;s[x][r];++r);
        for(l=y-1;s[x][l];--l);
        for(k=l+1,id_=id+get_id(x,k);k<r;++id_,++k)
        {
            if(s[x-1][k]&&*(id_-m)==-1)
            {
                q.push(x-1),Tm[t]=k,t++;
                for(id__=id_-m,kk=k;s[x-1][kk];--id__,--kk)*id__=dep_-1;
                for(id__=id_-m,kk=k;s[x-1][kk];++id__,++kk)*id__=dep_-1;
            }
            if(s[x+1][k]&&*(id_+m)==-1)
            {
                q.push(x+1),Tm[t]=k,t++;
                for(id__=id_+m,kk=k;s[x+1][kk];--id__,--kk)*id__=dep_+1;
                for(id__=id_+m,kk=k;s[x+1][kk];++id__,++kk)*id__=dep_+1;
            }
        }
    }
    if(mx==0)for(int k=l;k<=r;k++)s[x][k]=0;
    return mx;
}
inline int ksm(int x,int p)
{
    int res=1;
    for(;p;p>>=1,x=1ll*x*x%mod)if(p&1)res=1ll*x*res%mod;
    return res;
}
int main()
{
    n=read(),m=read();
    for(int i=1,opt;i<=n;i++)
    {
        for(opt=G();opt!='.'&&opt!='#';opt=G());
        for(int j=2;j<=m;j++)s[i][j]=G()-'#';
    }
    memset(id+1,-1,n*m*sizeof(int));

    //标记每个连通块的点并分配空间和去除深度为1的连通块 
    for(int i=1,*id_=id+1,now;i<=n;i++)
        for(int j=1;j<=m;++j,++id_)
            if(*id_==-1&&s[i][j])
                ++cnt,now=bfs(i,j,fir[cnt]=fir[cnt-1]+dep+1),cnt-=(now==0),dep=now?now:dep;

    for(int i=fir[cnt]+dep;i>=1;--i)Tm[i]=1;
    fir[cnt+1]=fir[cnt]+dep+1;

    //统计总方案数和每一连通块的方案后缀和 
    for(int i=n-1;i>=1;i--)
    {
        for(int j=2;j<m;j++)fa[j]=(s[i][j-1]?fa[j-1]:j),f[j]=1;
        for(int j=2,fx,fy;j<m;j++)
            if(s[i][j]&&s[i+1][j]&&(fx=get(j))!=(fy=get(j+m)))
                    f[fx]=1ll*f[fx]*f[fy]%mod,fa[fy]=fx;
        for(int j=2,*id_=id+get_id(i,j);j<m;++id_,++j)
            if(s[i][j]&&fa[j]==j)
                f[j]++,Tm[*id_]=1ll*Tm[*id_]*f[j]%mod;
        for(int j=2;j<m;j++)fa[j+m]=fa[j]+m;
        memcpy(f+m+1,f+1,sizeof(int)*m);
    }
    for(int i=0;i<=n;i++)sum[i]=mul[i]=1;

    //合并各个连通块的答案 
    for(int i=1,sm,sz,*T;i<=cnt;i++)
    {
        T=Tm+fir[i],sz=fir[i+1]-fir[i]-1,sm=*T;
        ans1=1ll*sm*ans1%mod,mx=max(mx,sz);
        mul[sz+1]=1ll*mul[sz+1]*sm%mod,sum[sz]=1ll*sum[sz]*sm%mod;
        for(int j=0;j<sz;j++)sum[j]=1ll*sum[j]*(sm+1-*(T+j+1))%mod;
    }
    for(int i=1;i<=mx;i++)mul[i]=1ll*mul[i]*mul[i-1]%mod,sum[i]=1ll*sum[i]*mul[i]%mod;
    for(int i=1;i<=mx;i++)ans2=(1ll*(sum[i]-sum[i-1])*i+ans2)%mod;
    printf("%lld",(1ll*ans2*ksm(ans1,mod-2)%mod+mod)%mod);
    return 0;
}