题解：P3208 [HNOI2010] 矩阵

· · 题解

不太懂爆搜为啥能过，所以这是一篇 2-SAT 题解。

设和矩阵为 s，原矩阵为 a。考虑用 a_{1,x} 和 a_{x,1} 表示 a_{i,j}。有 a_{i,j}=s_{i,j}-a_{i-1,j}-a_{i,j-1}-a_{i-1,j-1}。它的常数项 b_{i,j} 可以直接递推出来，剩下的部分是一个格路计数状物。对于没有拐弯的路线，它的权值是 (-1)^{len}；对于有拐弯的路线，把第一次拐弯换成走斜线刚好可以抵消。这个双射只有从 a_{1,1} 出发右下交替走到 a_{\min(i,j),\min(i,j)} 然后再走到 a_{i,j} 的路径会漏掉。所以 a_{i,j}=b_{i,j}+(-1)^{i+1}a_{1,j}+(-1)^{j+1}a_{i,1}+(-1)^{i+j+1}a_{1,1}。

所以我们可以枚举 a_{1,1}，然后就是形如 a_{1,i}+a_{j,1}\in[l,r] 的限制。把 a_{1,x} 和 a_{x,1} 拆成 p 个点后这些限制可以用 2-SAT 来刻画。令 V=np,E=n^2p，需要跑 p 次 2-SAT，1 次最小字典序，复杂度为 O(pE+VE)，无法通过。

但是可以使用 bitset 来求最小字典序 2-SAT，方法大致是缩点后维护每个点可达的点集，然后就可以容易判断这个点能否取 1。时间复杂度为变为 O(pE+\dfrac{VE}w)，可以通过。

下面这份代码的复杂度是 O(pE+\dfrac{VE}w+V^2) 的，因为我懒。

#include <bits/stdc++.h>
using namespace std;
int n,m,p,tot,b[205][205],pos[8005],top,cnt,stk[8005],s[205][205],a[205][205];
bitset<8005> to[8005],e[8005],fe[8005],g[2][8005],vis,cl; 
vector<int> cc[8005];
int id(int i,int j,int v,int op){
    return 2*((!i?j:i+m-1)-1)*p+(v-1)*2+op+1;
}
void Add(int u,int v){
//  cout<<"u,v:"<<u<<' '<<v<<'\n';
    e[u][v]=fe[v][u]=1;
}
void dfs(int x){
    vis[x]=0;
    for(int i=(vis&e[x])._Find_first();i<=tot;i=(vis&e[x])._Find_first())
        dfs(i);
    stk[++top]=x;
}
void dfs2(int x){
    vis[x]=0,pos[x]=cnt,cc[cnt].push_back(x);
    for(int i=(vis&fe[x])._Find_first();i<=tot;i=(vis&fe[x])._Find_first())
        dfs2(i);
}
int fd(int x){
    return x&1?x+1:x-1;
}
void col(int x,int v){
    if(!vis[x]) return ;
    cl[x]=v,vis[x]=0;
    for(int u:cc[x])
        if(vis[pos[fd(u)]])
            col(pos[fd(u)],v^1);
    for(int i=(vis&g[v][x])._Find_first();i<=cnt;i=(vis&g[v][x])._Find_first())
        col(i,v);
}
void solve(int x){
    for(int i=1;i<=tot;i++) e[i].reset(),fe[i].reset(),cc[i].clear();
    for(int i=1;i<m;i++){
        for(int j=1;j<p;j++)
            Add(id(0,i,j,0),id(0,i,j+1,0)),Add(id(0,i,j+1,1),id(0,i,j,1));
        Add(id(0,i,p,1),id(0,i,p,0));
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<p;j++)
            Add(id(i,0,j,0),id(i,0,j+1,0)),Add(id(i,0,j+1,1),id(i,0,j,1));
        Add(id(i,0,p,1),id(i,0,p,0));
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++){
            b[i][j]=s[i][j]+(i+j&1?x:-x);
            int l=1-b[i][j],r=p-b[i][j];
            if(i&1) l=-l,r=-r,swap(l,r);
//          cout<<"l,r:"<<l<<" "<<r<<'\n';
            if(i+j&1){
                if(l>p-1||r<1-p) return ;
                for(int k=1;k<=p;k++){
                    int v=k-l;
                    if(v>=1&&v<=p) Add(id(0,j,k,0),id(i,0,v,0));
                    else if(v<1) Add(id(0,j,k,0),id(0,j,k,1));
                    v=k-r;
                    if(v>=1&&v<=p) Add(id(0,j,k,1),id(i,0,v,1));
                    else if(v>p) Add(id(0,j,k,1),id(0,j,k,0));
                }
                l=-l,r=-r,swap(l,r);
                if(l>p-1||r<1-p) return ;
                for(int k=1;k<=p;k++){
                    int v=k-l;
                    if(v>=1&&v<=p) Add(id(i,0,k,0),id(0,j,v,0));
                    else if(v<1) Add(id(i,0,k,0),id(i,0,k,1));
                    v=k-r;
                    if(v>=1&&v<=p) Add(id(i,0,k,1),id(0,j,v,1));
                    else if(v>p) Add(id(i,0,k,1),id(i,0,k,0));
                }
            }
            else{
                if(l>2*p||r<2) return ;
                for(int k=1;k<=p;k++){
                    int v=l-k-1;
                    if(v>=1&&v<=p) Add(id(0,j,k,0),id(i,0,v,1)),Add(id(i,0,k,0),id(0,j,v,1));
                    else if(v>p) Add(id(0,j,k,0),id(0,j,k,1)),Add(id(i,0,k,0),id(i,0,k,1));
                    v=r-k-1;
                    if(v>=1&&v<=p) Add(id(0,j,k,1),id(i,0,v,0)),Add(id(i,0,k,1),id(0,j,v,0));
                    else if(v<1) Add(id(0,j,k,1),id(0,j,k,0)),Add(id(i,0,k,1),id(i,0,k,0));
                }
            }
        }
    vis.set(),top=0;
    for(int i=1;i<=tot;i++)
        if(vis[i])
            dfs(i);
    cnt=0;vis.set();
    for(;top;top--)
        if(vis[stk[top]])
            cnt++,dfs2(stk[top]);
    for(int i=1;i<=tot;i+=2)
        if(pos[i]==pos[i+1])
            return ;
//  cout<<cnt<<' '<<tot<<'\n';
    for(int i=1;i<=cnt;i++) g[0][i][i]=g[1][i][i]=to[i][i]=1;
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
            if(e[i][j])
                g[0][pos[i]][pos[j]]=g[1][pos[j]][pos[i]]=1;
    for(int i=cnt;i;i--)
        for(int j=i;j<=cnt;j++)
            if(g[0][i][j])
                to[i]|=to[j];
    vis.set();
    for(int i=1;i<tot;i+=2)
        if(vis[pos[i]]&&vis[pos[i+1]]){
            if((cl&to[pos[i]]).any()||to[pos[i]][pos[i+1]]) col(pos[i+1],0);
            else col(pos[i],0);
        }
    a[0][0]=x;
    for(int i=1;i<m;i++)
        for(int j=1;j<=p;j++)
            if(!cl[pos[id(0,i,j,0)]]){
                a[0][i]=j;
                break;
            }
    for(int i=1;i<n;i++)
        for(int j=1;j<=p;j++)
            if(!cl[pos[id(i,0,j,0)]]){
                a[i][0]=j;
                break;
            }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            a[i][j]=(i&1?-a[0][j]:a[0][j])+(j&1?-a[i][0]:a[i][0])+b[i][j];
    for(int i=0;i<n;cout<<'\n',i++)
        for(int j=0;j<m;j++)
            cout<<a[i][j]-1<<" ";
    exit(0);
}
int main(){
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m>>p,tot=(n+m-2)*2*p;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>s[i][j];
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            s[i][j]+=4,s[i][j]=s[i][j]-s[i-1][j]-s[i-1][j-1]-s[i][j-1];
    for(int i=1;i<=p;i++)
        solve(i);
    return 0;
}