题解 P4336 【[SHOI2016]黑暗前的幻想乡】

· · 题解

题意简述：

求在 n 条有色（n-1 种颜色）边中选 n-1 条 颜色各异 的边使它们构成一颗树的方案数。

题目解法：

前置知识：矩阵树定理

不会不行，有关系。

看到数据范围 (n\le17)，果断想到时间复杂度为 O(F2^n)，其中 F 为一个关于 n 的小（请感性理解）多项式。

我们看到，求生成树的个数，根据以往知识，肯定要用 \rm Matrix-Tree 定理了。

然后就是这个颜色各异条件特别烦，我们考虑枚举用的边从何处选出。

如果枚举用啥边，时间复杂度是 \mathcal{O}(\prod m_i n^3) 的，还不如暴力。

仔细想想，是因为 重复计数 了，每种情况都枚举了。

根据以往的经验，这道题数据规模又很小，所以用 容斥原理 就行了。

具体而言，就是 \mathcal{O}(2^n) 枚举只取其中几种颜色的边，然后瞎算一下就行了。

记 f 为只考虑某几种颜色时生成树的个数，则可以在 \mathcal{O}(n^3) 的时间复杂度算出一种选择方案所对应的 f 值。

更具体点，就是 \sum\limits_{\text{取 1 个}}f-\sum\limits_{\text{取 2 个}}f+\sum\limits_{\text{取 3 个}}f-\sum\limits_{\text{取 4 个}}f\cdots\pm\sum\limits_{\text{取 (n-1) 个}}f。

很显然，这个正负号取决于选的个数的奇偶性。

所以状压一下从 1 枚举到 2^{n-1}-1（\rm dfs 也行）顺便统计一下选的个数 \text{(cnt)} 然后容斥就行了。

具体详见代码。

正确代码：

#include<bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
using namespace std;
int TMP3301;
inline int read(){
    int res=0;
    char c;
    bool zf=0;
    while(((c=getchar())<'0'||c>'9')&&c!= '-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
int n;
int dta[21][21];
typedef pair<int,int>P;
vector<P>q[21];
inline void _swap(int x,int y){
    for(register int i=1;i<=n;++i){
        #define swap(x,y) TMP3301=x,x=y,y=TMP3301;
        swap(dta[i][x],dta[i][y]);
        #undef swap
    }
    return;
}
inline int det(){
    int ans=1;
    for(register int i=1;i<=n;++i){
        int p=-1;
        for(register int j=i;j<=n;++j)
            if(dta[i][j]){
                p=j;
                break;
            }
        if(!~p){
            return 0;
        }
        if(p!=i){
            _swap(i,p);
            ans*=-1;
        }
        for(register int j=i+1;j<=n;++j){
            while(dta[j][i]){
                int tmp=dta[j][i]/dta[i][i];
                for(register int k=i;k<=n;++k){
                    dta[j][k]-=1ll*tmp*dta[i][k]%mod;
                    dta[j][k]=(dta[j][k]%mod+mod)%mod;
                } 
                if(!dta[j][i]){
                    break;
                }
                swap(dta[i],dta[j]);
                ans*=-1;
            }
        }
        ans=1ll*ans*dta[i][i]%mod;
    }
    return ans;
}
signed main(){
    n=read()-1;
    for(register int i=1;i<=n;++i){
        int cnt=read();
        while(cnt--){
            int x=read(),y=read();
            q[i].push_back(mp(x,y));
        }
    }
    int ans=0;
    for(register int i=1;i<(1<<n);++i){
        memset(dta,0,sizeof(dta));
        int cnt=0;
        for(register int j=1;j<=n;++j){
            if(!(i&(1<<(j-1)))){
                continue;
            }
            ++cnt;
            for(register int k=0;k<q[j].size();++k){
                int x=q[j][k].first,y=q[j][k].second;
                ++dta[x][y],++dta[y][x],--dta[x][x],--dta[y][y];
            }
        }
        ans=(ans+((cnt&1)?-1:1)*det())%mod;
    }
    printf("%d\n",(ans%mod+mod)%mod);
    return 0;
}

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 \text{OIer}。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 \text{OIer}。