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

· · 题解

有那么一句话叫看到计数想容斥？

(为什么你会这么熟练啊！你到底切过多少道容斥题了啊！？)

但是容斥原理这个东西还是相当套路的，想不到就想不到了，但是熟练之后会切的很快~

相似题目可以去做一做P3349[ZJOI2016]小星星和这道题很像

但是这道题不是纯容斥，还是要加一些别的东西的

前置芝士：矩阵树定理

(只管瞎讲口胡不管证明，各位dalao们轻拍)

前置芝士的前置芝士：行列式

(正式的定义需要学习排列和逆序的相关知识，这里我们直接讲计算上的定义)

然后我们构造的定义一个方阵的行列式，行列式是一个数。

一个上三角方阵/下三角方阵(就是有一半全是0的矩阵)的行列式是其对角线之积

(特殊的，单位方阵行列式是1)

对于一方阵其一行/一列乘以k，行列式乘k

对于一方阵其两行相加减，行列式不变

对于一个矩阵交换其两行/两列，行列式反号

(推论，一个矩阵两行/两列成比例行列式为0)

好了那么我们发现我们可以从一个n阶单位方阵开始，仅凭借交换行/列，一行/一列乘k，行/列相加减这3个操作可以构造出所有的方阵，因此每个方阵都是有行列式的

那么我们怎么计算行列式呢？

我们发现只需要由单位矩阵/三角矩阵构造出来这个矩阵就行了对吧

我们发现构造用的3种操作(交换，加减，乘除)，刚好是高斯削元用的3种操作

所以我们对这个矩阵做一发高斯削元，会得到一个单位矩阵/三角矩阵

然后我们只需要将高斯削元中的每一步倒过来就可以构造出原矩阵然后就可以 求出行列式啦~

当然真实写代码的时候并不需要倒过来，只需要做高斯削元的时候交换就反号，乘变除除变乘，就可以一遍高斯削元一边求行列式了(如果你写的是削成单位矩阵的高斯削元，可以把行列式的初值直接设成1)

当然此时可能会发现最后消出来的矩阵对角线有0，我们此时直接return 0就好了

下面是矩阵树定理

矩阵树定理解决一个很简单的问题，一个无向图到底有多少个生成树？

答案和某个矩阵的行列式有关，这里我们只给出诸位dalao证明出来的结论

我们设这个图G的邻接矩阵是A,度数矩阵是D

(这里介绍下度数矩阵，度数矩阵只有对角线上不是0，第i行第i列的值是点i的度数，也就是邻接矩阵这一行的和)

(这里的邻接矩阵允许重边，邻接矩阵第i行第j列的值是i和j之间有几条边)

定义一个图的Kirchhoff矩阵K=D-A

那么矩阵树定理的结论如下

1.Kirchhoff矩阵同时去掉任意一行一列，剩下的矩阵行列式绝对值相等

2.Kirchhoff矩阵同时去掉任意一行一列，剩下的矩阵的行列式绝对值，就是这个无向图的生成树个数

求行列式的方法我们已经介绍，直接高斯削元暴力O(n^3)求解即可

(一个特例:完全图的生成树个数是n^{n-2})

本题题解：容斥原理

有了矩阵树定理这个暴力而优雅的定理之后这题就是一个考验诸位熟练度的容斥原理计数裸题了

我们可以认为这个题有两个限制

1.建造的公路构成一只生成树

2.每个公路必须由不同的公司建造

发现同时满足两个条件很辣手，但是呢我们可以只满足第一个条件

直接对着这个图跑一边矩阵树定理就可以求出方案数了对吧~

注意:如果两个公司可以建造同一个公路，需要按重边处理！

此时我们会发现我们明显算多了，刚好由n-1个公司建造的生成树是统计上了

但是我们也统计上了刚好由n-2个公司建造的生成树。

没关系，我们枚举到底是哪n-2个公司建造了这个树，显然这样的集合有C_{n-1}^{1}种，建图的时候只加入这n-2个公司的边，对着这个图跑一边矩阵树就可以求出方案数了对吧~，然后依次减去这些集合的方案数

但是我们发现此时明显算少了,因为我们多减去了刚好n-3个公司建造的树，显然这样的集合有C_{n-1}^{2}种，我们继续枚举集合，建图的时候只加入这n-3个公司的边，然后继续跑矩阵树定理，此时我们依次加上这些集合的方案数

然后发现我们加多了……n-4个公司的情况被重复统计了，此时我们以此类推地枚举所有的集合，最后显然一个公司都不剩的情况方案数是0，因此我们的递归是有终点的，并且当递归结束的时候我们刚好统计了所有的方案数。

以上建图时请务必注意重边的处理，同一边不同公司造按重边记！！！

算法复杂度O(2^{n-1}(n-1)^{3}log(10^{9}+7))可以通过此题(然而我常数极大差点T飞)

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=20;typedef long long ll;
ll mod=1e9+7;int n;int up;int mp[N][N];
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=(a*a)%mod){if(p&1){r=(r*a)%mod;}}return r;}
ll kir[N][N];int siz[262144];int u[N][N*N];int v[N][N*N];int m[N];ll res;
inline ll det()//行列式板子 
{
    ll res=1;int tr=0;//这里我们记录下到底反了多少次号，因为膜意义下取不了绝对值 
    for(int i=1;i<=n-1;i++)//强行高斯削元，不会的话出门左转luogu膜板区 
    {
        if(kir[i][i]==0)
        {
            for(int j=i+1;j<=n-1;j++)
            {
                if(kir[j][i]==0){continue;}tr^=1;//交换一次变一下号 
                for(int k=1;k<=n-1;k++){swap(kir[i][k],kir[j][k]);}
            }
        }
        for(int j=i;j<=n-1;j++)
        {
            if(kir[j][i]==0){continue;}//乘变除除变乘 
            ll div=po(kir[j][i],mod-2);res=(res*kir[j][i])%mod;
            for(int k=i;k<=n-1;k++){kir[j][k]=(kir[j][k]*div)%mod;}
        }
        for(int j=i+1;j<=n-1;j++)
        {
            if(kir[j][i]==0){continue;}
            for(int k=i;k<=n-1;k++){kir[j][k]=(kir[j][k]+mod-kir[i][k])%mod;}
        }
    }for(int i=1;i<=n-1;i++){res*=kir[i][i];}//判一下有没有0 
    return (tr)?(mod-res)%mod:res;//判一下是否反号 
}
int main()
{
    scanf("%d",&n);up=(1<<(n-1))-1;
    for(int i=1;i<n;i++)
    {scanf("%d",&m[i]);for(int j=1;j<=m[i];j++){scanf("%d%d",&u[i][j],&v[i][j]);}}
    for(int i=1;i<=up;i++){siz[i]=siz[i>>1]+(i&1);}//递推集合的siz 
    for(int i=1;i<=up;i++)
    {
        for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){kir[j][k]=0;}}//清空 
        for(int j=1,p=i;p;p>>=1,j++)//建图 
        {
            if((p&1)==0)continue;
            for(int k=1;k<=m[j];k++)
            {
                int U=u[j][k];int V=v[j][k];kir[U][U]++;kir[V][V]++;
                kir[U][V]=(kir[U][V]+mod-1)%mod;kir[V][U]=(kir[V][U]+mod-1)%mod;
            }
        }res=(res+mod+((n-siz[i])%2?det():-det()))%mod;//看一下删了多少个公司，决定符号 
    }printf("%lld\n",res);return 0;//拜拜程序~ 
}