题解：CF2097B Baggage Claim

· · 题解

首先如果两个相邻的点的曼哈顿距离不为 2 一定不合法，先判掉。

对于相邻的两个奇数点，如果他们是一条水平或者垂直的线，那么他们的中点一定要选，那么我们用 0 号点向其连接一条有向边。对于另外的情况，选择的可能有两种，我们将这两种选择的点连接一条无向边。

由于每个点只能选择一次，那么我们将问题转换为对我们新建的图给无向边定向，使得每个点的入度最大为 1。

由于 0 的出边已经确定，那么其所对于的连通块一定是棵树，否则答案为 0。

对于其他连通块（假设有 n 个点，m 条边），我们分讨：

  1. 如果是一棵树，那么我们可以选择一个定点使其没有入边，这样就有 n 中选择。
  2. 如果给定的是一颗基环树，可以知道只有环上正向和反向两种选择，故对答案的贡献是 2。
  3. 对于其他情况的答案就是 0（因为边数已经大于点数了，无论如何都有点的入度大于 1）。

对于不同连通块我们直接相乘即可。这样的复杂度是 O(nm) 的，可以通过。

Code

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e6+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}

template <int mod>
struct modint{

    int val;

    static int norm(const int &x){return x<0?x+mod:x;}
    static int Norm(const int &x){return x>=mod?x%mod:x;}

    modint inv()const{
        int a=val,b=mod,u=1,v=0,t;
        while(b>0)t=a/b,swap(a-=t*b,b),swap(u-=t*v,v);
        return modint(u);
    }

    modint():val(0){}
    modint(const int &m):val(norm(m)){}
    modint(const long long &m):val(norm(m%mod)){}
    modint operator -()const{return modint(norm(-val));}
    bool operator ==(const modint &x){return val==x.val;}
    bool operator !=(const modint &x){return val!=x.val;}
    bool operator <=(const modint &x){return val<=x.val;}
    bool operator >=(const modint &x){return val>=x.val;}
    bool operator >(const modint &x){return val>x.val;}
    bool operator <(const modint &x){return val<x.val;}
    modint& operator *=(const modint &x){return val=static_cast<int>(1ll*val*x.val%mod),*this;}
    modint& operator <<=(const modint &x){return val=(1ll*val<<x.val)%mod,*this;}
    modint& operator +=(const modint &x){return val=Norm(1ll*val+x.val),*this;}
    modint& operator -=(const modint &x){return val=norm(1ll*val-x.val),*this;}
    modint& operator >>=(const modint &x){return val>>=x.val,*this;}
    modint& operator ^=(const modint &x){return val^=x.val,*this;}
    modint operator >>(const modint &x){return modint(*this)>>=x;}
    modint operator <<(const modint &x){return modint(*this)<<=x;}
    modint& operator /=(const modint &x){return *this*=x.inv();}
    modint operator +(const modint &x){return modint(*this)+=x;}
    modint operator -(const modint &x){return modint(*this)-=x;}
    modint operator *(const modint &x){return modint(*this)*=x;}
    modint operator /(const modint &x){return modint(*this)/=x;}
    modint operator ^(const modint &x){return modint(*this)^=x;}
    friend std::ostream& operator<<(std::ostream& os,const modint &a){return os<<a.val;}
    friend std::istream& operator>>(std::istream& is,modint &a){return is>>a.val;}
};

typedef modint<1000000007>m17;

vector<int>v[Max];

int id[1010][1010];

void add(int x,int y){v[x].pb(y);v[y].pb(x);}

pii p[Max];

int vis[1010*1010];

int fa[Max];
int FindFa(int x){return x==fa[x]?x:fa[x]=FindFa(fa[x]);}
void merge(int x,int y){
    x=FindFa(x);y=FindFa(y);
    fa[x]=y;
}
int siz[Max],num[Max];
void dfs(int now){
    vis[now]=1;siz[now]=1;num[now]=v[now].size();
    for(auto to:v[now]){
        if(vis[to])continue;
        dfs(to);num[now]+=num[to];siz[now]+=siz[to];
    }
}

void work(){
    int n=read(),m=read(),k=read();int cnt=0;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)id[i][j]=++cnt;
    for(int i=0;i<=cnt;++i)v[i].clear(),vis[i]=siz[i]=num[i]=0;
    int tag=0;
    for(int i=1;i<=k+1;++i){
        int x,y;x=read();y=read();
        p[i]=mk(x,y);
        if(i!=1){
            if(abs(x-p[i-1].fi)+abs(y-p[i-1].se)!=2){
                tag=1;
            }
            if(abs(x-p[i-1].fi)==abs(y-p[i-1].se)){
                add(id[x][p[i-1].se],id[p[i-1].fi][y]);
            }else{
                add(0,id[(x+p[i-1].fi)/2][(y+p[i-1].se)/2]);
            }
        }
    }
    if(tag){
        cout << "0\n";
        return ; 
    }

    for(int i=0;i<=cnt;++i)fa[i]=i;
    for(int i=0;i<=cnt;++i){
        for(auto to:v[i]){
            merge(i,to);
        }
    }
    m17 ans=1;
    for(int i=1;i<=cnt;++i){
        if(FindFa(i)!=FindFa(0)&&!vis[i]){
            dfs(i);
            if(num[i]==siz[i]*2)ans*=2;
            else if(num[i]==(siz[i]-1)*2)ans*=siz[i];
            else ans=0;
        }
    }
    dfs(0);
    if(num[0]!=(siz[0]-1)*2)ans=0;
    cout << ans << "\n";
}

bool Med;
signed main(){
    int T=read();
    while(T--)work();

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/