题目来源于牛客竞赛：https://ac.nowcoder.com/acm/contest/discuss
题目描述：

输入描述：

输出描述：

示例1：

题解：

代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
  
#define fi first
#define se second
#define mp make_pair
#define pb push_back
  
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = (1e9 + 7);
void radd(int &a, int b)
{
    a+=b;
    while(a>=MOD) a-=MOD;
}
 
int add(int a, int b)
{
    a+=b;
    while(a>=MOD) a-=MOD;
    return a;
}
int mult(int a, int b)
{
    return (a*1LL*b)%MOD;
}
int modpow(int a, int b)
{
    int r=1;
    while(b)
    {
        if(b&1) r=mult(r,a);
        a=mult(a,a);
        b>>=1;
    }
    return r;
}
int inverse(int a)
{
    return modpow(a,MOD-2);
}
void init(int _n)
{
    fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
    fact.resize(_n+1);
    ifact.resize(_n+1);
    inv.resize(_n+1);
    pow2.resize(_n+1);
    pow2[0]=1;
    ifact[0]=1;
    fact[0]=1;
    for(int i=1;i<=_n;i++)
    {
        pow2[i]=add(pow2[i-1],pow2[i-1]);
        fact[i]=mult(fact[i-1],i);
        //ifact[i]=mult(ifact[i-1],inv[i]);
    }
    ifact[_n] = inverse(fact[_n]);
    for(int i=_n-1;i>=1;i--)
    {
        ifact[i] = mult(ifact[i + 1], i + 1);
    }
    for(int i=1;i<=_n;i++)
    {
        inv[i] = mult(fact[i-1],ifact[i]);
    }
}
 
const int M = 12;
const int N = 155;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
const int C = 4;
 
struct DSU
{
    int S;
    struct node
    {
        int p;
    };
    vector<node> dsu;
    DSU(int n)
    {
        S = n;
        for(int i = 0; i < n; i++)
        {
            node tmp;
            tmp.p = i;
            dsu.pb(tmp);
        }
    }
    int rt(int u)
    {
        if(dsu[u].p == u) return u;
        dsu[u].p = rt(dsu[u].p);
        return dsu[u].p;
    }
    void merge(int u, int v)
    {
        u = rt(u); v = rt(v);
        if(u == v) return ;
        if(rand()&1) swap(u,v);
        dsu[v].p = u;
    }
};
 
map<vi,int> ma;
vi F[555];
const int C2 = 76;
 
vi horizontal_connect(vi conn, int bit)
{
    vi nw(C,0);
    DSU dsu(C*2+3);
    assert(conn.size()==C);
    int cur=C+1;
    for(int i=0;i+1<conn.size();i++)
    {
        if(bit&(1<<i))
        {
            if(conn[i]==0) conn[i]=cur++;
            if(conn[i+1]==0) conn[i+1]=cur++;
            dsu.merge(conn[i],conn[i+1]);
        }
    }
    int ID[C*2+3]; memset(ID,-1,sizeof(ID)); int c=1;
    ID[0]=0;
    for(int i=0;i<conn.size();i++)
    {
        if(conn[i]>0&&(dsu.rt(conn[i])==conn[i])&&ID[conn[i]]==-1)
        {
            ID[conn[i]]=c++;
        }
    }
    for(int i=0;i<conn.size();i++)
    {
        nw[i] = ID[dsu.rt(conn[i])];
    }
    int msiz=ma.size(); assert(msiz<C2);
    if(ma.find(nw)==ma.end()) {ma[nw]=msiz-1; F[msiz-1]=nw;}
    return nw;
}
 
vi vertical_connect(vi conn, int bit)
{
    vi nw(C,0); assert(conn.size()==C); set<int> S; set<int> S2;
    for(int i=0;i<conn.size();i++)
    {
        S2.insert(conn[i]);
        if(bit&(1<<i))
        {
            nw[i]=conn[i]; S.insert(nw[i]);
        }
    }
    S2.erase(0); S.erase(0);
    if(S.size()!=S2.size()) return {};
    int msiz=ma.size(); assert(msiz<C2);
    if(ma.find(nw)==ma.end()) {ma[nw]=msiz-1; F[msiz-1]=nw;}
    return nw;
}
 
int dp[N+11][(1<<C)+1][C2+1][(1<<C)+1];
 
int g(int id)
{
    vi tmp=F[id]; int bit=0;
    for(int i=0;i<C;i++)
    {
        if(tmp[i]>0) bit^=(1<<i);
    }
    return bit;
}
 
int solve_fast2(vector<ii> vec)
{
    int n = vec.size();
    if(vec.empty()) return 0;
    set<ii> S;
    for(int i=0;i<n;i++) S.insert(vec[i]);
    int ans = 0;
    //count odd degree vertices
    for(int i=0;i<N;i+=2)
    {
        for(int j=0;j<M;j+=2)
        {
            int ex=0;
            for(int d=0;d<4;d++)
            {
                if(S.find(mp(i+dx[d],j+dy[d]))!=S.end())
                {
                    ex=1; break;
                }
            }
            if(ex) ans=add(ans,pow2[n-1]);
        }
    }
    //count eulerian cycles
    ma.clear();
    ma[{}]=-1;
    vi emp(C,0); ma[emp]=0; F[0]=emp;
    memset(dp,0,sizeof(dp));
    dp[0][0][0][0]=1;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<(1<<C);j++)
        {
            for(int k=0;k<C2;k++)
            {
                for(int l=0;l<(1<<C);l++)
                {
                    if(dp[i][j][k][l]==0) continue;
                    int v=dp[i][j][k][l];
                    if(i%2==0)
                    {
                        for(int bit=0;bit<(1<<(C-1));bit++)
                        {
                            bool pos=1; int j2=j;
                            for(int z=0;z<C-1;z++)
                            {
                                //connect (i,2z) with (i,2(z+1)) using (i,2z+1)
                                if((bit&(1<<z))>0&&S.find(mp(i,2*z+1))==S.end())
                                {
                                    pos=0; break;
                                }
                                if(bit&(1<<z)){j2^=(1<<z); j2^=(1<<(z+1));}
                            }
                            if(!pos) continue;
                            vi conn = F[k];
                            vi nw = horizontal_connect(conn, bit);
                            int cnt = 0;
                            //count new bad edges here
                            for(int z=0;z<C;z++)
                            {
                                if(conn[z]==0&&nw[z]>0) //(i,2z) just became bad
                                {
                                    if(S.find(mp(i-1,2*z))!=S.end() && !(l&(1<<z)))
                                    {
                                        cnt++;
                                    }
                                    if(S.find(mp(i+1,2*z))!=S.end())
                                    {
                                        cnt++;
                                    }
                                    //spread to left and right
                                    if(S.find(mp(i,2*z+1))!=S.end()&&conn[z+1]==0)
                                    {
                                        cnt++;
                                    }
                                    if(S.find(mp(i,2*z-1))!=S.end()&&nw[z-1]==0)
                                    {
                                        cnt++;
                                    }
                                }
                            }
                            radd(dp[i+1][j2][ma[nw]][g(k)], mult(v, inv[(1<<cnt)]));
                        }
                    }
                    else
                    {
                        for(int bit=0;bit<(1<<C);bit++)
                        {
                            bool pos=1; int j2=j;
                            for(int z=0;z<C;z++)
                            {
                                //connect (i-1,2z) and (i+1,2z) with (i,2z)
                                if((bit&(1<<z))>0&&S.find(mp(i,2*z))==S.end())
                                {
                                    pos=0; break;
                                }
                                if(bit&(1<<z)){j2^=(1<<z);}
                            }
                            if(!pos) continue;
                            if(j2!=0) continue; //or else no eulerian cycle
                            vi conn = F[k];
                            vi nw = vertical_connect(conn, bit);
                            if(nw.empty()) continue;
                            int cnt=0;
                            //count new bad edges here
                            //impossible for (i-1,2z) to be bad but become good now by parity
                            for(int z=0;z<C;z++)
                            {
                                if(nw[z]>0) //(i+1,2z) just became bad, push to all 4 directions
                                {
                                    //up not needed
                                    if(S.find(mp(i+2,2*z))!=S.end())
                                    {
                                        cnt++;
                                    }
                                    //spread to left and right
                                    if(S.find(mp(i+1,2*z+1))!=S.end())
                                    {
                                        cnt++;
                                    }
                                    if(S.find(mp(i+1,2*z-1))!=S.end()&&nw[z-1]==0)
                                    {
                                        cnt++;
                                    }
                                }
                            }
                            radd(dp[i+1][bit][ma[nw]][g(k)], mult(v, inv[(1<<cnt)]));
                        }
                    }
                }
            }
        }
    }
    vi good;
    for(auto X:ma)
    {
        if(X.fi.empty()) continue;
        int mx=0;
        for(int i=0;i<X.fi.size();i++)
        {
            mx=max(mx,X.fi[i]);
        }
        if(mx==1) good.pb(X.se);
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<(1<<C);j++)
        {
            for(int k:good)
            {
                for(int l=0;l<(1<<C);l++)
                {
                    if(i%2==1&&j==0) ans=add(ans, mult(2, mult(pow2[n], dp[i][j][k][l])));
                }
            }
        }
    }
    ans = mult(ans, inv[2]);
    return ans;
}
 
int solve_fast(vector<ii> vec)
{
    int n = vec.size();
    vector<ii> V[2];
    for(int i=0;i<n;i++)
    {
        if((vec[i].fi+vec[i].se)%2==0)
        {
            vec[i].se++;
            V[0].pb(vec[i]);
        }
        else
        {
            V[1].pb(vec[i]);
        }
    }
    int ans = 0;
    for(int i=0;i<2;i++)
    {
        int sol = solve_fast2(V[i]);
        ans = add(ans, mult(pow2[int(V[i^1].size())], sol));
    }
    return ans;
}
 
void read_solve()
{
    int n; cin>>n;
    vector<ii> vec;
    for(int i=0;i<n;i++)
    {
        int x,y; cin>>x>>y;
        vec.pb(mp(x,y));
    }
    cout<<solve_fast(vec)<<'\n';
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init(255555);
    read_solve();
}

更多问题，更详细题解可关注牛客竞赛区，一个刷题、比赛、分享的社区。
传送门：https://ac.nowcoder.com/acm/contest/discuss