【BZOJ 3812】 3812: 主旋律（容斥原理**）

痛定思痛。 2021-10-01 00:08 302阅读 0赞

> ## 3812: 主旋律 ##
> 
> Time Limit: 10 Sec  Memory Limit: 256 MB  
> Submit: 235  Solved: 196
> 
> ## Description ##
> 
> 响应主旋律的号召，大家决定让这个班级充满爱，现在班级里面有 n 个男生。
> 
> 如果 a 爱着 b，那么就相当于 a 和 b 之间有一条 a→b 的有向边。如果这 n 个点的图是强联通的，那么就认为这个班级是充满爱的。
> 
> 不幸的是，有一些不好的事情发生了，现在每一条边都可能被摧毁。我作为爱的使者，想知道有多少种摧毁的方式，使得这个班级任然充满爱呢？（说人话就是有多少边的子集删去之后整个图仍然强联通。）
> 
> ## Input ##
> 
> 第一行两个数 n 和 m，表示班级里的男生数和爱的关系数。
> 
> 接下来 m 行，每行两个数 a 和 b，表示男生 a 爱着男生 b。同时 a 不等于 b。
> 
> 所有男生从 1 到 n 标号。
> 
> 同一条边不会出现两遍，但可能出现 a 爱着 b，b 也爱着 a 的情况，这是两条不同的边。
> 
> ## Output ##
> 
> 输出一行一个整数,表示对 109+7 取模后的答案。
> 
> ## Sample Input ##
> 
> 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 ##
> 
> 9390
> 
> ## HINT ##
> 
> 对于 100% 的数据满足: n≤15,0≤m≤n(n−1)。
> 
> ## Source ##
> 
> [2015年国家集训队测试][2015]
> 
>

【分析】

此乃神题也！

看了好久题解啊。。【想不出来还不懂。。

嗯。。要ORZ[男神][Link 1]。。他的题解好懂多了。

> 　　题解都看了一天才看懂TAT。。  
>      考虑求出非强联通即dag的方案数用全部情况减  
>      注意统计dag从出度为0的点入手，这题中就是缩点后出度为0的点  
>      先考虑一个辣鸡做法  
>      若现全集为s，我们已经知道某种方案子集t会缩成k个强连通分量,这些强连通分量出入度都为0  
>      那么我们可以得出s至少缩成k个出度0强连通分量的一类方案数(即用t中这k个限制最小的方案)为2^x(x为s^t里的点为起点，s里的点为终点的边数)。因为这x条边的所有连     法，包括了所有缩点后有大于等于k个的方案。  
>         (容斥很重要的一点就是设置“至少为。。” 状态，注意“至少k状态”应包含所有“为x状态”，其中k是x的子集  
> 　　然后我们就上容斥，对于至少k个出度0的方案，当k为奇数时就减，当k为偶数时就加  
> 　　现在考虑正解  
> 　　我们枚举一个子集的某种方案，看他的出度0个数是奇还是偶太慢了  
> 　　注意对于一种方案我们关心的只是他是哪个点集，他缩完点后有奇数个出度为0还是偶数个出度为0，其中奇数时就-1，偶数时就+1  
> 　　那我们可以设g\[s\]表示s这个点集所有缩点成若干个强连通分量方案的贡献和，其中缩成奇数个的方案贡献-1，偶数的贡献+1  
> 　　设f\[s\]表示s为一个强连通方案数，s内部有h\[s\]条边，那么  
> 　　f\[s\]=2^h\[s\]+sigma (2^cnt) \* g\[t\]  
> 　　t为s的子集，cnt为起点在s^t中,终点在t中的边数  
> 　　注意这一步是已经带上容斥的，因为g\[t\]是容斥贡献和  
> 　　然后  
> 　　g\[s\]=-f\[t\] \* g\[s^t\] - f\[s\];  
> 　　其中t为包含s最小标号节点子集。g表示缩为若干个出度0强连通，t就是枚举最小标号所在强连通，这样保证情况不重不漏。前面的-代表，加入t这个强连通分量后，原来方案的强连通数奇偶取反，所以贡献正负取反。最后-f\[s\]就表示单独s这一个强连通分量，因为1是奇数，所以每种方案贡献是-1  
> 　　然后就做完辣owo

一个DAG肯定由一些没有出度的点构成，那么我们可以考虑枚举没有出度的点的子集T。那么S-T中的边和S-T 到T之间的边也可以随便连。

但是我们这样连出来不能保证S-T中没有出度为0的点（或者强联通分量）。而且有可能会重复计算。【这个要用容斥

比如说两个出度为0的点u,v，枚举T=\{u\}的和T=\{v\}时都会计算u,v。 【这个我们枚举s的最小节点集就可以避免这样的重复

g数组的意思，其实是把s分成若干个互不影响的强联通块的方案数的和，求和时要冠以符号$(-1)^t$,t表示分成了多少个强联通块。【容斥部分

这个是方便容斥的。不然你枚举了处于T集合的点之后还要枚举强联通块慢死

关于容斥方面。

男神说的很好。就是，容斥重点是“至少k。。。”

要算至少有k个出度为0，就是减掉。。。，加上。。。

Ans=总数-非强联通个数

非强联通即缩点后的DAG的个数>=2。

最后只要枚举处于T集合的点，然后累加就好，因为在g数组里面考虑了容斥的正负号了。

不懂也可以看代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<cstring>
     4 #include<iostream>
     5 #include<algorithm>
     6 using namespace std;
     7 typedef long long LL;
     8 #define Maxn (1<<15)+10
     9 #define N 20
    10 #define M 410
    11 #define Mod 1000000007
    12 #define LL long long
    13 
    14 int ru[N],chu[N];
    15 int pw[M],h[Maxn],w[Maxn],d[Maxn];
    16 int g[Maxn],f[Maxn],num[Maxn];
    17 
    18 void init(int n,int m)
    19 {
    20     pw[0]=1;for(int i=1;i<=m;i++) pw[i]=1LL*pw[i-1]*2%Mod;
    21     for(int i=1;i<=n;i++) w[1<<i-1]=i,chu[i]=ru[i]=0;
    22     for(int i=1;i<(1<<n);i++) d[i]=d[i>>1]+(i&1);
    23 }
    24 
    25 int lowbit(int x) {
          return x&(-x);}
    26 
    27 int main()
    28 {
    29     int n,m;
    30     scanf("%d%d",&n,&m);
    31     init(n,m);
    32     for(int i=1;i<=m;i++)
    33     {
    34         int x,y;
    35         scanf("%d%d",&x,&y);
    36         ru[y]|=1<<x-1;
    37         chu[x]|=1<<y-1;
    38     }
    39     int ss=(1<<n)-1;
    40     for(int i=1;i<=ss;i++)
    41     {
    42         int x=lowbit(i),y=w[x];
    43         h[i]=h[i^x]+d[chu[y]&i]+d[ru[y]&i];
    44         f[i]=pw[h[i]];g[i]=0;
    45         
    46         for(int j=(i-1)&i;j;j=(j-1)&i)
    47         {
    48             if(j&x) continue;
    49             g[i]=(g[i]-1LL*g[j]*f[i^j]%Mod)%Mod;
    50         }
    51         for(int j=i;j;j=(j-1)&i)
    52         {
    53             if(j==i) num[i^j]=0;
    54             else
    55             {
    56                 x=lowbit(i^j);y=w[x];
    57                 num[i^j]=num[i^j^x]+d[chu[y]&i];
    58             }
    59             f[i]=(f[i]+1LL*g[j]*pw[num[i^j]]%Mod)%Mod;
    60         }
    61         g[i]=(g[i]-f[i])%Mod;
    62     }
    63     f[ss]=(f[ss]+Mod)%Mod;
    64     printf("%d\n",f[(1<<n)-1]);
    65     return 0; 
    66 }

2017-04-19 19:49:29

转载于:https://www.cnblogs.com/Konjakmoyu/p/6735264.html

[2015]: http://www.lydsy.com/JudgeOnline/problemset.php?search=2015%E5%B9%B4%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E6%B5%8B%E8%AF%95
[Link 1]: http://la1la1la-blog.logdown.com/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/f1d4e1e7cf774699b77ce0a270922682.png