[容斥+矩阵树定理]bzoj4596: [Shoi2016]黑暗前的幻想乡

题目描述

四年一度的幻想乡大选开始了,最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡,扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪(人类)博丽灵梦和八云紫等人整日高谈所有妖怪平等,幻想乡多元化等等,对于幻想乡目前面临的种种大问题却给不出合适的解决方案。

风间幽香是幻想乡里少有的意识到了问题的严重性的大妖怪。她这次勇敢的站了出来参加幻想乡大选。提出包括在幻想乡边境建墙(并让人类出钱),大力开展基础设施建设挽回失业率等一系列方案,成为了大选年出人意料的黑马并顺利的当上了幻想乡的大统领。

幽香上台以后,第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市,之间原来没有任何路。幽香向选民承诺要减税,所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司,每个建筑公司都想在修路的过程中获得一些好处。

虽然这些建筑公司在选举前没有给幽香钱,幽香还是打算和他们搞好关系,因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。

每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边,然后每条边都交给一个能够负责该边的建筑公司修建,并且每个建筑公司都恰好修一条边。

幽香现在想要知道一共有多少种可能的方案呢?两个方案不同当且仅当它们要么修的边的集合不同,要么边的分配方式不同。

输入

第一行包含一个正整数 N(N<=17), 表示城市个数。

接下来 N-1 行,其中第 i行表示第 i个建筑公司可以修建的路的列表:

以一个非负数mi 开头,表示其可以修建 mi 条路,接下来有mi 对数,

每对数表示一条边的两个端点。其中不会出现重复的边,也不会出现自环。

输出

仅一行一个整数,表示所有可能的方案数对 10^9 + 7 取模的结果。

样例输入

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

样例输出

17

来源

By 佚名上传

题解

如果上来直接大力矩阵树,那么算出来的值中有些公司可能没有修路;

如果把每个公司可以修的路去掉,再跑一遍矩阵树,得出来的就是保证有个公司没有路,前后一减就可以保证有个公司必定修了路;

继续下去,这就是一个容斥,每次枚举那些公司没有路,在矩阵中减去,刷一趟矩阵树,按照容斥加减一波即可;

#include<cstdio>
#include<cstring>
#include<algorithm>
#define _x first
#define _y second
#define tt 1000000007
using namespace std;
int N,P[20],f=1;
pair<int,int>Num[20][405];
long long Ans;
long long qsm(long long A,long long B){
    long long Sum=1;A%=tt;
    while (B){
        if (B&1) Sum=(Sum*A)%tt;
        A=(A*A)%tt;B>>=1;
    }
    return Sum;
}
struct Martix{
    long long A[20][20];
    void clear(){memset(A,0,sizeof A);}
    long long det(){
        long long Res=1,F=1;
        for (int i=1;i<N;i++){
            int id=0;
            for (int j=N-1;j>=i;j--) if (A[j][i]) id=j;
            if (!id) return 0;
            if (id!=i){
                Res=(-Res+tt)%tt;
                for (int j=i;j<=N;j++) swap(A[id][j],A[i][j]);
            }
            for (int j=i+1;j<N;j++){
                long long t=(A[j][i]*qsm(A[i][i],tt-2))%tt;
                for (int k=i;k<N;k++) A[j][k]=(A[j][k]-(t*A[i][k])%tt+tt)%tt;
            }
        }
        for (int i=1;i<N;i++) Res=(Res*A[i][i])%tt;
        return (Res*F+tt)%tt;
    }
}M,Cal;
void DFS(int x){
    if (x==N){
        Cal=M;
        Ans=(Ans+f*Cal.det()+tt)%tt;
        return ;
    }
    DFS(x+1);
    for (int j=1;j<=P[x];j++){
        M.A[Num[x][j]._x][Num[x][j]._y]++;
        M.A[Num[x][j]._y][Num[x][j]._x]++;
        M.A[Num[x][j]._x][Num[x][j]._x]--;
        M.A[Num[x][j]._y][Num[x][j]._y]--;
    }
    f=-f;
    DFS(x+1);
    for (int j=1;j<=P[x];j++){
        M.A[Num[x][j]._x][Num[x][j]._y]--;
        M.A[Num[x][j]._y][Num[x][j]._x]--;
        M.A[Num[x][j]._x][Num[x][j]._x]++;
        M.A[Num[x][j]._y][Num[x][j]._y]++;
    }
    f=-f;
}
int main()
{
    scanf("%d",&N);
    for (int i=1;i<N;i++){
        scanf("%d",&P[i]);
        for (int j=1;j<=P[i];j++){
            scanf("%d%d",&Num[i][j]._x,&Num[i][j]._y);
            M.A[Num[i][j]._x][Num[i][j]._y]--;
            M.A[Num[i][j]._y][Num[i][j]._x]--;
            M.A[Num[i][j]._x][Num[i][j]._x]++;
            M.A[Num[i][j]._y][Num[i][j]._y]++;
        }
    }
    DFS(1);
    printf("%lld\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注