UOJ37

UOJ , 评论

UOJ37

Description

响应主旋律的号召，大家决定让这个班级充满爱，现在班级里面有 个男生。

如果 爱着 ，那么就相当于 和 之间有一条 的有向边。如果这 个点的图是强联通的，那么就认为这个班级是充满爱的。

不幸的是，有一些不好的事情发生了，现在每一条边都可能被摧毁。我作为爱的使者，想知道有多少种摧毁的方式，使得这个班级任然充满爱呢？（说人话就是有多少边的子集删去之后整个图仍然强联通。）

Input

第一行两个数 和 ，表示班级里的男生数和爱的关系数。

接下来 行，每行两个数 和 ，表示男生 爱着男生 。同时 不等于 。

所有男生从 到 标号。

同一条边不会出现两遍，但可能出现 爱着 ， 也爱着 的情况，这是两条不同的边。

Output

输出一行一个整数，表示对 取模后的答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5 15
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1

Sample Output

1
9390

Constraints

对于 的数据满足: ;

对于 的数据满足: ;

对于 的数据满足: ;

对于 的数据满足: 。

时间限制：1s

空间限制：256MB

Solution

表示把集合 分为非强连通分量的方案数

表示把集合 分为 个 的方案数

表示把集合 分为 个 的方案数（也即是 ） 定义其中的 对于 , 令 后两项可以通过预处理一个点的出度集合和入度集合来快速计算

Q： 算 时要用到 但算 时不是应该加上当前的 吗， 又要通过 求？

A: 想一下我们现在求的是什么：当前情况的合法状态数 。这个要通过 实现，那么就要把之前算的答案导致的不合法情况容斥掉，而 的意义只是为了我们后面再算的时候降低复杂度，是我们“定义”出来的一个值，没有什么实际含义，即我们只需要算之前的 导致的不合法情况并删除，剩下的就是现在合法的情况数，然后再用这个去更新现在的 以便以后用到的时候值正确

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define ll long long
#define FIO "uoj37"
#define cnt(x) __builtin_popcount(x)
using namespace std;

const int N=15,N2=N*N,SN=1<<N,MOD=1e9+7;

inline int add(int a,const int &b){return (a+=b)>=MOD?a-MOD:a;}
inline int sub(int a,const int &b){return (a-=b)<   0?a+MOD:a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}

int n,m,up;
int E[SN],f[SN],g[SN],ans[SN],bin[N2],edge[SN],id[SN],d[N][N],in[N],out[N];

int main(){
  freopen(FIO".in","r",stdin);
  freopen(FIO".out","w",stdout);

  scanf("%d%d",&n,&m);
  up=1<<n;
  for(int i=0;i<n;i++)id[1<<i]=i;
  bin[0]=1;for(int i=1;i<N2;i++)bin[i]=add(bin[i-1],bin[i-1]);

  for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),d[--u][--v]++,in[v]|=1<<u,out[u]|=1<<v;

  for(int S=1;S<up;S++){
    int lst=S&-S;
    E[S]=E[S^lst]+cnt(in[id[lst]]&(S^lst))+cnt(out[id[lst]]&(S^lst));
  }

  for(int S=1;S<up;S++){
    int lst=S&-S;
    if(S==lst){
      g[S]=ans[S]=1;
      continue;
    }
    edge[S]=0;
    for(int T=(S-1)&S;T;T=(T-1)&S){
      int lst=(S^T)&-(S^T);
      edge[T]=edge[T^lst]-cnt(out[id[lst]]&(T^lst^S))+cnt(in[id[lst]]&T);
    }

    for(int T=(S^lst)&((S^lst)-1);~T;T=T?(T-1)&(S^lst):-1){
      dec(g[S],mul(ans[T^lst],g[T^lst^S]));
    }

    for(int T=S;T;T=(T-1)&S){
      inc(f[S],mul(g[T],bin[edge[T]+E[S^T]]));
    }

    inc(g[S],ans[S]=sub(bin[E[S]],f[S]));
  }

  printf("%d\n",ans[up-1]);

  return 0;
}

​

不知不觉Acmer & Student

Never Settle