Solution P11776 | Yet Another D**n Training

· · 题解

一个莫名其妙的题。

将所有在多边形内的点视作黑点，否则视作白点。

则一个黑白染色方案能对应一个合法的多边形的充要条件是：

左上、右下同色，左下、右上同色，左上、左下异色。

条件 1 很好处理。条件 3 可以利用 K 很小的性质，暴力维护扫描到当前列，目前这一列 K 个格子的连通状态（状态数 \operatorname{Bell}(K) < 1000）。暴搜预处理出所有状态即可。

枚举当前列的各个黑色连通状态 S，再枚举下一列的黑白状态 T。令 f(S,T) 表示其后继状态编号，若不合法则记作 0。

为了让连通状态 S 更形象化，我们给每个黑点一个编号（白点编号为 0），编号相同的黑点在一个连通块中。

以下是计算 f(S,T) 的流程：

  1. 判断条件 1。若不合法则为 0。
  2. 将当前列的连通状态继承到下一列（可以将连通块编号直接复制过去，前提是下一列中对应位置要是黑点）。

如果当前列的某个连通块在下一列中丢失（即这个连通块的所有点在下一列中的对应位置均为白点，无法继承），则不合法。

如果下一列中的某个黑点在当前列中的对应位置为白点（没有可以继承的），则新加一个连通块。

  1. 把在下一列中的两个相邻黑点对应的连通块合并起来。从左到右合并，同时判断条件 2。

若在合并位于 x 和 x+1 处的黑点时，发现它们本来就是同一个连通块，则会形成一个包围圈。但是这个包围圈有可能没有包围白点（例：2 \times 2 的全黑矩形）。事实上只需要判当前列中 x 处是不是白点即可，这里可以自行思考一下为什么）

直接一列一列 DP 过去即可。注意要求最后一个有黑点的列中的所有黑点在同一个连通块中。

const int mod = 10007;
inline void addmod(int &x){ if(x >= mod) x -= mod; }

int n,k,cur=0,now[10];
int seq[1005][10], cnt, f[1005][100];
void dfs(int x){
    if(x==k){
        ++cnt;
        for(int i=0;i<k;i++) seq[cnt][i]=now[i];
        return;
    }
    for(int i=0;i<=cur;i++){
        now[x]=i; dfs(x+1);
    }
    cur++; now[x]=cur; dfs(x+1); cur--;
}

int tmp[10], fa[10], czy[10], lcq[10], vis[10];
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

int dp[1005][1005];
void procedure(){
    k=read(),n=read();
    dfs(0);

    for(int i=1;i<=cnt;i++){
        for(int j=0;j<(1<<k);j++){
            for(int l=0;l<k;l++) tmp[l]=(j>>l)&1;
            bool flg=0, debug=(i==3&&j==1);
            for(int l=0;l+1<k;l++){
                if(seq[i][l] && tmp[l+1] && !tmp[l] && !seq[i][l+1]) flg=1;
                if(seq[i][l+1] && tmp[l] && !tmp[l+1] && !seq[i][l]) flg=1;
            }
            if(flg) continue; 

            memset(czy,0,sizeof(czy)); memset(vis,0,sizeof(vis));
            memset(lcq,0,sizeof(lcq));

            for(int l=0;l<k;l++) 
                if(tmp[l]) czy[l]=seq[i][l], vis[seq[i][l]]=1;

            int lzy = 0;
            for(int l=0;l<k;l++){
                lzy = max(lzy, seq[i][l]);
                if(seq[i][l] && !vis[seq[i][l]]) flg=1;
            }
            if(flg) continue;

            for(int l=0;l<k;l++)
                if(tmp[l]) if(!czy[l]) czy[l]=(++lzy);   

            assert(lzy <= k); 

            for(int l=1;l<=lzy;l++) fa[l]=l;

            for(int l=1;l<k;l++){
                if(czy[l] && czy[l-1]){
                    int x=find(czy[l-1]), y=find(czy[l]);
                    if(x==y && !seq[i][l-1]) flg=1;
                    fa[x]=y;
                }
            }
            if(flg) continue;

            for(int l=0;l<k;l++)
                if(czy[l]) lcq[l]=find(czy[l]);
                else lcq[l]=0;

            memset(vis,0,sizeof(vis));

            int fjy=0;
            for(int l=0;l<k;l++){
                if(!lcq[l]) continue;

                if(!vis[lcq[l]]) vis[lcq[l]]=(++fjy);
                lcq[l]=vis[lcq[l]];
            }

            for(int t=1;t<=cnt;t++){
                bool flg=1;
                for(int l=0;l<k;l++) flg&=(lcq[l]==seq[t][l]);
                if(flg){
                    f[i][j] = t;
                    break;
                }
            }
        }
    }

    int ans = 0;
    dp[0][1]=1;
    for(int i=0;i<n;i++){
        for(int m=1;m<=cnt;m++)
        for(int j=0;j<(1<<k);j++){
            if(!f[m][j]) continue;
            addmod(dp[i+1][f[m][j]] += dp[i][m]);
        }
        for(int m=1;m<=cnt;m++){
            int mx=0;
            for(int l=0;l<k;l++) mx=max(mx, seq[m][l]);
            if(mx==1) addmod(ans += dp[i+1][m]);
        }
    }
    printf("%d\n", ans);
}