[清华集训 2014] 主旋律

UOJ #37.

思路

考虑如何容斥。设$a_i$为图被划分为至少$i$个强连通分量的方案数,则有$$\text{ans}=\sum \limits_{i=1}^{n}(-1)^{i-1}a_i$$

而被划分为至少$i$个强连通分量这个说法我们可以转化一下,就当是钦定缩点后$i$个强连通分量都是入度不为$0$的,那么剩下的点向所有点就可以随便连了。

设$f_S$为对于诱导子图$S$的答案,$g_S$为对于点集$S$形成奇数个强连通分量的方案数减去$S$形成偶数的强连通分量的方案数,$e(S, T)$为点集$S$到点集$T$的边数,那么有$$\begin{split}f_S &=2^{e(S, S)}-\sum \limits_{\varnothing \not =T \subset S} g_T\cdot 2^{e(S, S-T)}\\ g_S &=\sum \limits_{\varnothing \not =T \subset S} -f_{S-T}\cdot g_T +f_S\end{split}$$

代码

#include <iostream>
#include <cstdio>
#include <vector>

template <typename T> void in(T &_){
  char c=getchar(); _=0; int fl=1;
  while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
  while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

const int MOD=1e9+7;
int N, M, f[1<<15], g[1<<15], h[16][1<<15], bit[1<<15];
bool map[16][16];

inline int lowbit(int x){return x&(-x);}
inline int ksm(int x, int y){
  int z=1;
  for(; y; y>>=1, x=1LL*x*x%MOD) if(y&1) z=1LL*z*x%MOD;
  return z;
}

void print(int x){
  for(int i=0; i<N; i++) putchar('0'+((x>>i)&1));
}

int main(){
  int x, y;
  in(N); in(M);
  for(int i=1; i<=M; i++){
    in(x); in(y);
    map[x][y]=true;
  }
  for(int i=0; i<N; i++) bit[1<<i]=i+1;
  for(int i=1; i<=N; i++)
    for(int j=1; j<(1<<N); j++)
      h[i][j]=h[i][j-lowbit(j)]+map[i][bit[lowbit(j)]];
  for(int i=1; i<(1<<N); i++){
    int tot=0, one=lowbit(i), sta=i^one;
    for(int j=1; j<=N; j++) if((i>>(j-1))&1)
      tot+=h[j][i];
    f[i]=ksm(2, tot);
    for(int j=sta; j; j=sta&(j-1)) 
      g[i]=(g[i]-1LL*f[i^j]*g[j]%MOD)%MOD;
    for(int j=i; j; j=i&(j-1)){
      tot=0;
      for(int k=1; k<=N; k++) if((i>>(k-1))&1)
        tot+=h[k][i^j];
      f[i]=(f[i]-1LL*g[j]*ksm(2, tot)%MOD)%MOD;
    }
    g[i]=(g[i]+f[i])%MOD;
  }
  printf("%d\n", (f[(1<<N)-1]+MOD)%MOD);
  return 0;
}

发表评论

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