题解：P17097 [ICPC 2017 Qingdao R] Hex Game

· · 题解

题意简述

给定一个已有若干棋子的 Hex 棋盘。白棋先手，双方每次都从当前空格中等概率随机选择一个位置。求白棋连接上下边界与黑棋连接左右边界的概率。

解题思路

先考虑游戏结束后的棋盘。连接一旦形成，继续落子不会使它断开。因此可以在胜负已经确定后，仍按照原来的落子次序填完所有空格。填满的 Hex 棋盘一定恰有一方完成自己的连接目标，所以延长游戏不会改变胜者。

设初始有 m 个空格。白棋在这些位置中落下 k=\left\lceil\frac{m}{2}\right\rceil 枚棋子，黑棋占据其余位置。指定最终由白棋占据的 k 个空格后，白棋的落子顺序有 k! 种，黑棋的落子顺序有 (m-k)! 种。故每种这样的最终染色都对应 k!(m-k)! 个完整落子序列，出现概率相同。只需计算白棋获胜的最终染色数占全部合法染色数的比例。

直接枚举 \binom{m}{k} 种染色不可行，但棋盘宽度只有 8。按行优先顺序处理格子，并在已处理区域与未处理区域的交界处维护连通性。处理完 (x,y) 后，每一列只需保留一个格子：第 0\sim y 列保留当前行，第 y+1\sim n-1 列保留上一行。任何仍可能延伸到未处理区域的白色连通块都会与这条轮廓相交。

用状态 s 记录轮廓上各位置所属的白色连通块，每个位置占四位：

只有连通关系有用，普通连通块的编号没有实际含义。生成新状态时，从左到右为它们依次分配 2,3,\dots，接触顶边的连通块则始终使用编号 1。这种规范化保证相同的轮廓划分只保存一次。

代码用并查集完成一次状态转移。先将旧状态中编号相同的位置合并，再将编号为 1 的位置与虚拟顶点 top 合并。若当前格填成白色，则为它建立新点 cur。在行优先扫描顺序下，当前格已经处理过的邻格只有：

若邻格为白色，就把它与 cur 合并。第一行的白格还要与 top 合并。若当前格填成黑色，则第 y 个轮廓位置不保留任何节点。最后扫描更新后的轮廓：与 top 同根的位置写入 1，其余非空根按出现顺序重新编号。

令 f_{s,c} 表示处理完当前前缀后，状态为 s，且已有 c 个初始空格填成白色的方案数。初始状态为 f_{0,0}=1。初始棋子决定每格允许的转移：W 只能填白，B 只能填黑，. 可以任选一种颜色。预置棋子不计入 c；只有 . 选择白色时，才从 c 转移到 c+1。

可以对扫描前缀归纳证明状态含义始终成立。空前缀没有白色连通块。加入一个格子时，并查集恢复了旧状态的全部等价类，并加入当前格通向前缀的全部 Hex 邻边，所以新的连通划分准确。离开轮廓的连通块与未处理区域之间已经没有边，以后不可能重新出现，故丢弃它不会损失信息。

固定一种合法最终染色后，每个 . 的颜色唯一确定，扫描过程中也就只有一条对应的转移路径。反过来，任意一条走到 c=k 的路径都确定了一种合法最终染色。因此 f 既不会漏计，也不会重复计数。

全部格子处理完后，轮廓位于最后一行。状态中含有编号 1，等价于某个底边白格与顶边连通。将这些状态的 f_{s,k} 求和得到白棋获胜方案数，将所有状态的 f_{s,k} 求和得到总方案数。两者相除即为白棋概率，黑棋概率为其补集。

设可达轮廓状态数为 S。共有 n^2 次逐格转移，每个状态至多产生两条转移；恢复和规范化连通关系需要 O(n^2)，维护白棋数量需要 O(m)。时间复杂度为 O(n^2S(n^2+m))，空间复杂度为 O(Sm)。最大计数不超过 \binom{64}{32}，可以用 unsigned long long 保存。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
using ld=long double;
const int N=9;
const int K=33;
using num=array<ull,K>;
int n;
int fa[N*2+1];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(int u,int v){fa[find(u)]=find(v);}
ull trans(ull s,int x,int y,bool white)
{
    int a[N]={};
    for(int i=0;i<n;i++)a[i]=s>>(i*4)&15;
    for(int i=0;i<=n+1;i++)fa[i]=i;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)if(a[i]&&a[i]==a[j])merge(i,j);
    }
    int cur=n,top=n+1;
    for(int i=0;i<n;i++)if(a[i]==1)merge(i,top);
    if(white)
    {
        if(!x)merge(cur,top);
        if(a[y])merge(cur,y);
        if(y&&a[y-1])merge(cur,y-1);
        if(y+1<n&&a[y+1])merge(cur,y+1);
    }
    int id[N*2+1]={},cnt=2;
    ull res=0;
    for(int i=0;i<n;i++)
    {
        if(i==y&&!white)continue;
        int u=find(i==y?cur:i),v;
        if(u==find(top))v=1;
        else
        {
            if(!id[u])id[u]=cnt++;
            v=id[u];
        }
        res|=(ull)v<<(i*4);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(6);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        char a[N][N];
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                cnt+=a[i][j]=='.';
            }
        }
        int need=(cnt+1)/2,cur=0;
        unordered_map<ull,num> f,g;
        f.reserve(4096);
        f[0][0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                g.clear();
                g.reserve(f.size()*2+1);
                int d=a[i][j]=='.';
                for(auto &[s,v]:f)
                {
                    if(a[i][j]!='W')
                    {
                        auto &w=g[trans(s,i,j,0)];
                        for(int k=0;k<=cur&&k<=need;k++)w[k]+=v[k];
                    }
                    if(a[i][j]!='B')
                    {
                        auto &w=g[trans(s,i,j,1)];
                        for(int k=0;k<=cur&&k+d<=need;k++)w[k+d]+=v[k];
                    }
                }
                f.swap(g);
                cur+=d;
            }
        }
        ull sum=0,win=0;
        for(auto &[s,v]:f)
        {
            sum+=v[need];
            bool ok=0;
            for(int i=0;i<n;i++)if((s>>(i*4)&15)==1)ok=1;
            if(ok)win+=v[need];
        }
        ld ans=(ld)win/sum;
        cout<<"White "<<ans<<" Black "<<1-ans<<'\n';
    }
    return 0;
}