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

题解

前置芝士 :矩阵树定理

本题是一道计数题，有两个要求：

建造的公路构成一颗生成树
每条公路由不同的公司建造，每条公路与一个公司一一映射

那么看到这两个要求后，我们很容易想到第一个条件用矩阵树定理，那么对于第二个条件，我们就很容易想到容斥原理。

先不考虑第二个条件，把所有边都加进去（没有自环），这是我们用矩阵树原理算出来的结果不仅有 \(n-1\) 个公司建造的方案，也包括了 \((n-2)...1\) 个公司建造的方案。

此时，我们需要减去 \(n-2\) 个公司建造的方案，那么这里我们就把其中一个公司去掉，再进行计算，注意这里去掉一个公司有 \(n-1\) 种方案。

但是我们会发现 \(n-3\) 个公司建造的方案被重复减去了，所以我们需要加回来，至此，就是一个纯的容斥了。

对于删去不同的公司，计算不同的方案，我们可以用二进制压一下 \(n-1\) ，二进制每一位 \(1\) 代表选取这一位代表的公司。

而在求解行列式的过程中，我们可以直接利用逆元进行求解，也可以辗转相除。

所以最后前一种复杂度为 \(\mathcal O(2^{n-1}((n-1)^3+(n-1)log(1e9+7)))\) 后一种的复杂度为 \(\mathcal O(2^{n-1}(n-1)^3logn)\) 。

Code

逆元 \(AC \kern 0.4em CODE:\)

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    inline int read() {

        ri x=0,f=1;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        return x*f;

    }

}

using IO::read;

namespace nanfeng{

    #define lm(x) (1<<x)

    #define lowbit(x) (x&-(x))

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    typedef long long ll;

    static const int N=20,MOD=1e9+7;

    int num[N],u[N][N*N],v[N][N*N],G[N][N],siz[lm(16)+7],lg[lm(16)+7]={-1},n,cnt,st,ans;

    inline void add(int u,int v) {p(G[u][v]),p(G[v][u]);}

    inline int fpow(int x,int y) {

        int res=1;

        while(y) {

            if (y&1) res=1ll*res*x%MOD;

            x=1ll*x*x%MOD;y>>=1;

        }

        return res;

    }

    inline int Gauss() {

        int res=1,tr=0;

        for (ri i(1);i<=cnt;p(i)) {

            for (ri j(i+1);j<=cnt;p(j)) if (G[j][i]) {swap(G[i],G[j]);tr^=1;break;}

            int inv=fpow(G[i][i],MOD-2);

            for (ri j(i+1);j<=cnt;p(j)) {

                int tmp=1ll*inv*G[j][i]%MOD;

                for (ri k(i+1);k<=cnt;p(k)) G[j][k]=(G[j][k]-1ll*G[i][k]*tmp%MOD+MOD)%MOD;

            }

            if (!G[i][i]) return 0;

            res=1ll*res*G[i][i]%MOD;

        }

        return tr?-res:res;

    }

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        n=read(),cnt=n-1;st=(1<<n-1)-1;

        for (ri i(1);i<=st;p(i)) siz[i]=siz[i>>1]+(i&1),lg[i]=lg[i>>1]+1;

        for (ri i(1);i<n;p(i)) {

            num[i]=read();

            for (ri j(1);j<=num[i];p(j)) u[i][j]=read(),v[i][j]=read();

        }

        for (ri i(1);i<=st;p(i)) {

            int low=i;

            memset(G,0,sizeof(G));

            while(low) {

                int id=lg[lowbit(low)]+1;

                for (ri j(1);j<=num[id];p(j)) add(u[id][j],v[id][j]);

                low-=lowbit(low);

            }

            for (ri j(1);j<=n;p(j)) {

                for (ri k(1);k<=n;p(k)) if (j^k) G[j][j]+=G[j][k],G[j][k]=-G[j][k];

            }

            // for (ri j(1);j<=n;p(j)) {

            //     for (ri k(1);k<=n;p(k)) printf("%d ",G[j][k]);

            //     puts("");

            // }

            int tmp=(Gauss()+MOD)%MOD;

            // printf("state=%d tmp=%d\n",i,tmp);

            ans=((ll)ans+MOD+((n-siz[i])&1?tmp:-tmp))%MOD;

        }

        printf("%d\n",ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

Code

辗转相除法 \(AC \kern 0.4em CODE:\)

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    inline int read() {

        ri x=0,f=1;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        return x*f;

    }

}

using IO::read;

namespace nanfeng{

    #define lm(x) (1<<x)

    #define lowbit(x) (x&-(x))

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    typedef long long ll;

    static const int N=20,MOD=1e9+7;

    int num[N],u[N][N*N],v[N][N*N],G[N][N],siz[lm(16)+7],lg[lm(16)+7]={-1},n,cnt,st,ans;

    inline void add(int u,int v) {p(G[u][v]),p(G[v][u]);}

    inline int Gauss() {

        int res=1,tr=0;

        for (ri i(1);i<=cnt;p(i)) {

            for (ri j(i+1);j<=cnt;p(j)) {

                while(G[j][i]) {

                    int k=G[i][i]/G[j][i];

                    for (ri l(i);l<=cnt;p(l)) G[i][l]=(G[i][l]-(ll)G[j][l]*k%MOD)%MOD;

                    swap(G[i],G[j]);tr^=1;

                }

            }

            if (!G[i][i]) return 0;

            res=(ll)res*G[i][i]%MOD;

        }

        return tr?-res:res;

    }

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        n=read(),cnt=n-1;st=(1<<n-1)-1;

        for (ri i(1);i<=st;p(i)) siz[i]=siz[i>>1]+(i&1),lg[i]=lg[i>>1]+1;

        for (ri i(1);i<n;p(i)) {

            num[i]=read();

            for (ri j(1);j<=num[i];p(j)) u[i][j]=read(),v[i][j]=read();

        }

        for (ri i(1);i<=st;p(i)) {

            int low=i;

            memset(G,0,sizeof(G));

            while(low) {

                int id=lg[lowbit(low)]+1;

                for (ri j(1);j<=num[id];p(j)) add(u[id][j],v[id][j]);

                low-=lowbit(low);

            }

            for (ri j(1);j<=n;p(j)) {

                for (ri k(1);k<=n;p(k)) if (j^k) G[j][j]+=G[j][k],G[j][k]=-G[j][k];

            }

            // for (ri j(1);j<=n;p(j)) {

            //     for (ri k(1);k<=n;p(k)) printf("%d ",G[j][k]);

            //     puts("");

            // }

            int tmp=(Gauss()+MOD)%MOD;

            // printf("state=%d tmp=%d\n",i,tmp);

            ans=((ll)ans+MOD+((n-siz[i])&1?tmp:-tmp))%MOD;

        }

        printf("%d\n",ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

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

题解

最新文章

热门文章