【UOJ#37】 [清华集训2014] 主旋律

雨点打透心脏的1/2处 2021-11-17 04:28 231阅读 0赞

[题目链接][Link 1]

# 题目描述 #

给定一张强联通图,求有多少种边的存在情况满足图依然强联通。  
\\(n\\leq15\\)

# Sol #

首先正难则反,考虑用总数减去不强联通的。

考虑一张不强联通的图，缩点后一定是一个 DAG，好像可以对 DAG 进行计数。  
诈一看这个做不了，因为缩点后计数是不可能在dp过程中实现的。

但我们按照 DAG 计数的思路的话其实并不需要真的知道 DAG 缩点后的形态。

我们类似 DAG 计数的话那么枚举这些缩完点后的点至少有多少个入度为 0 的点，然后容斥计算。

过程中我们用到的只是有 奇数/偶数个 入度为0的点的方案数以及他们和外部连边的总方案数。

所以我们只需要设 \\(g\[s\]/h\[s\]\\) 分别表示 集合 \\(s\\)的导出子图 内有 奇数/偶数 个入度为0的强联通分量的方案数。设 \\(f\[s\]\\) 表示 \\(s\\) 集合导出子图强联通的方案数，\\(cnt(S,T)\\) 表示 \\(S\\) 到 \\(T\\) 内的边数。

\\(f\\)的转移和 DAG 计数类似。g，h的转移都很简单:

\\\[f\[S\]=2^\{cnt(S,S)\}-\\sum\_\{T\\subseteq S , T \\neq \\emptyset\}(g\[T\]-h\[T\])\*2^\{cnt(S-T,S-T)+cnt(T,S-T)\}\\\]

\\\[g\[S\]=\\sum\_\{T\\subseteq S,T\\neq \\emptyset\} f\[T\]\*h\[S-T\]\\\]  
\\\[h\[S\]=\\sum\_\{T\\subseteq S,T\\neq \\emptyset\} f\[T\]\*g\[S-T\]\\\]

发现好像 \\(g\\),\\(h\\) 和 \\(f\\) 会互相转移。  
分析一下，由于 \\(g\[0\]=0\\) 所以 \\(h\\) 的转移不受影响。然后 \\(g\[S\]\\) 的转移需要加上 \\(f\[S\]\\) , \\(f\[S\]\\) 的转移似乎也需要 \\(g\\) 来支持。  
但是注意到我们算的东西是不强联通的,因此整个一大坨就是一个强联通分量的话是不能被算入 \\(f\\) 的,也就是说 \\(g\[S\]\\) 要靠 \\(f\[S\]\\) 来进行转移的部分恰好不能贡献到 \\(f\[S\]\\) 里面去，所以我们先算出 \\(g\\),\\(h\\) ，然后直接按照原来的方法算 \\(f\\) ，算完之后载把 \\(f\[S\]\\) 加入 \\(g\[S\]\\) 就可以了。

code:

#include<bits/stdc++.h>
    #define Set(a,b) memset(a,b,sizeof(a))
    using namespace std;
    const int MAXN=225;
    const int N=16;
    const int MAXS=1<<(N-1);
    const int mod=1e9+7;
    template <typename T> inline void init(T&x){
        x=0;char ch=getchar();bool t=0;
        for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
        for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
        if(t) x=-x;return;
    }
    typedef long long ll;
    template<typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}
    template<typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}
    template<typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
    inline int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}
    inline int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}
    int f[MAXS],g[MAXS],h[MAXS];
    bitset<MAXN> in[MAXS],out[MAXS];
    inline int Cnt(int S,int T){return (out[S]&in[T]).count();}
    int bits[MAXN],cnt[MAXS];int n,m;
    
    int main()
    {
        init(n),init(m);bits[0]=1;
        for(int i=1;i<MAXN;++i) bits[i]=Sum(bits[i-1],bits[i-1]);
        const int UP=1<<n;
        for(int i=1;i<=m;++i) {
            int u,v;init(u),init(v);
            for(int s=1;s<UP;++s) {
                if(s&bits[u-1]) out[s].set(i);
                if(s&bits[v-1]) in [s].set(i);
            }
        }f[0]=0,g[0]=0,h[0]=1;// g: odd / h: even
        
        for(int s=1;s<UP;++s) {
            cnt[s]=cnt[s>>1]+(s&1);f[s]=0;int lb=s&(-s);
            for(int t=s;t;t=(t-1)&s) if(t&lb) Inc(g[s],(ll)f[t]*h[s^t]%mod),Inc(h[s],(ll)f[t]*g[s^t]%mod);
            for(int t=s;t;t=(t-1)&s) Inc(f[s],(ll)Dif(g[t],h[t])*bits[Cnt(t,s^t)+Cnt(s^t,s^t)]%mod);
            f[s]=Dif(bits[Cnt(s,s)],f[s]);
            Inc(g[s],f[s]);
        }
        printf("%d\n",f[UP-1]);
        return 0;
    }

转载于:https://www.cnblogs.com/NeosKnight/p/10876846.html

[Link 1]: http://uoj.ac/problem/37