UOJ37. 【清华集训2014】主旋律

http://uoj.ac/problem/37

题解

题目是让我们求出有多少个边集可以使这张图强连通。

先补集转化一下，求这张图不强连通的方案数。

我们考虑这样的图缩完点之后的情况，既然不强连通，那么它就是个\(DAG\)。

回顾一下有向图\(DAG\)计数的方法。

每次新加入一层入度为\(0\)的点，向之前的点连边。但这时我们不能保证我们枚举的点就是全部入度为\(0\)的，所以我们还需要容斥。

\[f[S]=\sum_{T\subset S}(-1)^{|T|}f[S-T]2^{edge(S,S-T)}
\]

再次观察到容斥系数之和点数的奇偶性有关，因为此时我们的每个点已经是一个强连通分量了。

所以我们设\(deg[s]\)表示\(s\)集合是一个\(DAG\),如果求出了这个数组，那么我们用全集减去它就是答案了。

我们再设\(D[s]\)表示\(s\)集合被划分为奇数个强连通分量的方案数，\(S[s]\)表示划分为偶数个强连通分量的方案数。

转移：

\[dag[S]=\sum_{T\subset S}(D[S]-S[S])*2^{edge(T,S-T)+edge(S-T,S-T)}
\]

最后加上自己连自己的方案数是因为我们的容斥系数已经弄好了，只需要让\(S-T\)缩完点之后成为一个\(DAG\)就行了，所以合法的边集是全集。

我们最后的答案\(f[s]\)表示\(s\)集合强连通的方案数，\(D\)和\(S\)的转移有：

\[D[S]=\sum_{T\subset S}f[T]*S[S-T]
\]

\[S[S]=\sum_{T\subset S}f[T]*D[S-T]
\]

代码

#include<bits/stdc++.h>

#define N 16

#define M 225

using namespace std;

typedef long long ll;

const int mod=1e9+7;

int n,m;

ll D[1<<N],S[1<<N],ci[N*N],f[1<<N];

bitset<M>in[1<<N],out[1<<N];

inline void MOD(ll &x){x=x>=mod?x-mod:x;}

inline ll rd(){

  ll x=0;char c=getchar();bool f=0;

  while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

  return f?-x:x;

}

inline int calc(int s,int t){return (out[s]&in[t]).count();}

int main(){

  n=rd();m=rd();

  int u,v;

  int maxn=(1<<n)-1;

  ci[0]=1;

  for(int i=1;i<=n*n;++i)ci[i]=ci[i-1]*2%mod;

  for(int i=1;i<=m;++i){

    u=rd();v=rd();

    for(int j=1;j<=maxn;++j){

      if(j&(1<<u-1))out[j][i]=1;

      if(j&(1<<v-1))in[j][i]=1;

    }

  }

  S[0]=1;

  for(int i=1;i<=maxn;++i){

    f[i]=ci[calc(i,i)];

    for(int s=(i-1)&i;s;s=(s-1)&i){

      MOD(f[i]=(f[i]-(D[s]-S[s])*ci[calc(s,i-s)+calc(i-s,i-s)]%mod+mod));

      if((s&(i&-i))==0)continue;

      MOD(D[i]+=f[s]*S[i-s]%mod);

      MOD(S[i]+=f[s]*D[i-s]%mod);

    }

    MOD(f[i]=(f[i]-(D[i]-S[i]))%mod+mod);

    MOD(D[i]+=f[i]);

  }

  cout<<f[maxn];

  return 0;

}

巴特西

UOJ37. 【清华集训2014】主旋律

题解

代码

最新文章

热门文章