题解：P3427 [POI 2005] DZI-Hollows

· · 题解

简单计数。

首先手玩一些样例可知，给出的图中若存在环，则无解，所以图一定是一个森林。

考察其中一个大小至少为 2 的联通块。这个联通块一定是由一条链以及链上的节点挂的叶子组成的。这个联通块可以左右翻转、上下翻转，且一个节点上挂的叶子可以排列，因此一个联通块的方案数为 4\prod\limits_u(|E_u|-\sum\limits_v\left[|E_v|\ge 2\right])!，其中 E_x 表示 x 连的边集合。需要注意的是，如果是一个菊花图则上下不能翻转，需要特判。

然后考虑联通块之间的组合。先放所有大小至少为 2 的 c_2 个，因为这些联通块一定两边都有点，无法交叉，方案数是 c_2!。然后放 c_1 个单点，可以任意放一个空位，方案数为 (c_1+c_2+2)^{\underline{c_1}}。全部乘起来就是最终答案。

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+6;
int n,m,mod,f[N],fac[N];
bool vis[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
vector<int>pos[N],edge[N];
bool dfs(int p,int fa){
    vis[p]=1;
    for(int x:edge[p])if(x!=fa){
        if(vis[x])return 1;
        if(dfs(x,p))return 1;
    }return 0;
}
void solve(){
    cin>>n>>m>>mod;
    for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,edge[x].push_back(y),edge[y].push_back(x),f[find(x)]=find(y);
    for(int i=1;i<=n;i++)if(!vis[i]&&dfs(i,0)){cout<<"0\n";return;}
    for(int i=1;i<=n;i++)pos[find(i)].push_back(i);
    int c1=0,c2=0,ans=1;
    for(int i=1;i<=n;i++){
        if(pos[i].size())
            if(pos[i].size()==1)c1++;
            else c2++,ans=2ll*ans%mod;
        bool fl=0;
        for(int x:pos[i]){
            int c=0;
            for(int y:edge[x])if(edge[y].size()>=2)c++;
            if(c==0)ans=1ll*ans*fac[edge[x].size()]%mod;
            else if(c==1)ans=1ll*ans*fac[edge[x].size()-1]%mod,fl|=edge[x].size()>=2;
            else if(c==2)ans=1ll*ans*fac[edge[x].size()-2]%mod;
            else{cout<<"0\n";return;}
        }if(fl)ans=2ll*ans%mod;
    }ans=1ll*ans*fac[c2]%mod;
    for(int i=n-c1+2;i<=n+1;i++)ans=1ll*ans*i%mod;
    cout<<ans<<'\n';
}
signed main(){
    clock_t _st=clock();
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)solve();
    clock_t _ed=clock();
    cerr<<(_ed-_st)*1.0/CLOCKS_PER_SEC<<'\n';
    return 0;
}