题解：CF2097B Baggage Claim

· · 题解

题目传送门：洛谷 || CF

神秘分类讨论题。赛时两罚才过。/kk

蒟蒻的做法可能更为麻烦一些。

题目大意

一条路径是合法的，当且仅当每次只能走到相邻格子，且一个格子不能经过两次。现在有一条长为奇数的路径，不告诉你其中第偶数个格子，问有多少种合法填法。

题目分析

首先有几种情况可以特判掉，方便后续处理：

发现可能有多个填法的只有一种情况：|x_{i+1}-x_i|=1,|y_{i+1}-y_i|=1。这时只能在 (x_i,y_{i+1}),(x_{i+1},y_i) 中选一个，且不能重复选这个点。于是在这两个点间连边，那么就变成了在一个图中给每条边选两端点中一个且不能重复的方案数。

但先等等。有的点其实是不能被选的。当 |x_{i+1}-x_i|=2 或 |y_{i+1}-y_i|=2 时，(\frac{x_i+x_{i+1}}{2},\frac{y_i+y_{i+1}}{2}) 不能被选。我们对这些点打标记。

对图中的每个联通块都数出其中点数 a，标记过的点数 b，边数 c。此时有很多种情况：

最后把每个联通块的答案乘起来就行了。

AC Code

// by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
//bool Mst;
const int N=1e6+5,mod=1e9+7;
vector<int> g[N];
int x[N],y[N],to[N],used[N];
array<int,3> dfs(int u,int fa)
{
    to[u]=1;
    array<int,3> ans={1,used[u],(int)g[u].size()};
    for(int v:g[u]) if(v!=fa&&!to[v])
    {
        auto res=dfs(v,u);
        ans[0]+=res[0],ans[1]+=res[1],ans[2]+=res[2];
    }
    return ans;
}
//bool Med;
signed main()
{
//  cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) [&]()
    {
        int n,m,k,cnt=0,ans=1;
        cin>>n>>m>>k;k++;
        vector<vector<int>> num(n+2,vector<int>(m+2));
        for(int i=1;i<=n*m;i++) g[i].clear(),to[i]=0,used[i]=0;
        for(int i=1;i<=k;i++) cin>>x[i]>>y[i];
        for(int i=1;i<k;i++)
            if(abs(x[i]-x[i+1])+abs(y[i]-y[i+1])!=2)
            {
                cout<<0<<"\n";
                return;
            }
        for(int i=1;i<k;i++)
        {
            if(x[i]==x[i+1]||y[i]==y[i+1])
            {
                int xx=(x[i]+x[i+1])/2,yy=(y[i]+y[i+1])/2;
                if(!num[xx][yy]) num[xx][yy]=++cnt;
                if(used[num[xx][yy]])
                {
                    cout<<0<<"\n";
                    return;
                }
                used[num[xx][yy]]=1;
            }
        }
        for(int i=1;i<k;i++)
        {
            if(abs(x[i]-x[i+1])==1)
            {
                if(!num[x[i]][y[i+1]]) num[x[i]][y[i+1]]=++cnt;
                if(!num[x[i+1]][y[i]]) num[x[i+1]][y[i]]=++cnt;
                g[num[x[i]][y[i+1]]].push_back(num[x[i+1]][y[i]]);
                g[num[x[i+1]][y[i]]].push_back(num[x[i]][y[i+1]]);
            }
        }
        for(int i=1;i<=cnt;i++) if(!to[i])
        {
            auto p=dfs(i,0);p[2]/=2;
            if(p[2]<p[0])
            {
                if(!p[1]) ans=1ll*ans*p[0]%mod;
                else if(p[1]>1)
                {
                    cout<<0<<"\n";
                    return;
                }
            }
            else if(p[2]==p[0])
            {
                if(!p[1]) ans=1ll*ans*2%mod;
                else
                {
                    cout<<0<<"\n";
                    return;
                }
            }
            else
            {
                cout<<0<<"\n";
                return;
            }
        }
        cout<<ans<<"\n";
    }();
    return 0;
}