清华集训2014 主旋律

题面

lk好菜啊….

大部分还是看Sengxian的博客学的……

题解

设:

$f_S$表示S中的点组成一个联通块的方案数。

$g_S$表示S中点组成一个DAG(不止一个联通块)的方案数。

$h_s$表示首尾都在S中的边数。

那么显然$f_S=2^{h_S}-g_S$。

$f_S$很难算,“正难则反”我们可以通过计算$g_S$来得到$f_S$。

我们设$c_S$表示S中点组成一些联通块(块之间没有边)的方案数。

$g_S$计算时可以通过枚举出度为0的联通块来计算。这就需要用到容斥。

我们可以直接把$c_S$的定义改成 S中点组成奇数个联通块方案数 - S中点组成偶数个联通块方案数。

注意这个方案指的是留下的边集而不是分成的联通块。

就可以通过选定一个点,枚举包含这个点的联通块然后计算$c_S$。

显然$C_\emptyset=0$
$$
c_S=f_S-\sum_{\substack{T\subset S\k\in T}}f_Tc_{S-T}
$$

表示枚举包含点k的联通块T,然后计算。

这个-表示多了一个联通块所以取反。

通过枚举出度为0的联通块集合T,我们可以得到$g_S$的递推公式:

$$
g_S=\sum_{\substack{T\subset S\T\not=\emptyset}}2^{h_{S-T}+e_{S-T,T}}c_{T}\
f_S=2^{h_S}-\sum_{\substack{T\subset S\T\not=\emptyset}}2^{h_{S-T}+e_{S-T,T}}c_{T}
$$

$h$刚刚定义了,$e_{S,T}$表示从S集合中点到T集合中点的边数。

这个表示,枚举出度为0的联通块,其它的点之间的边和到这些联通块上的边都是可选可不选的,因为有容斥。

慢着!有问题!

在$g_S$的公式中,$S=T$时,$c_T$会包含$f_S$ 也就是只有一个联通块的情况,但是$g_S$和$f_S$是对立的(不止一个联通块),并且这样的话计算$f_S$会需要$c_S$的值,$c_S$又需要$f_S$的值,这就会出问题。

那就$c_S$先不加$f_S$,算出$g_S$当然还有$f_S$以后再加就可以了。

对于$h_{S}$和$e_{S,T}$,可以直接$O(n2^n)$和 $O(3^n)$预处理。

由于需要枚举子集,$f_S$和$c_S$的计算也是$O(3^n)$的。

所以直接$O(3^n)$完美的AC了。

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
63
64
65
66
67
68
69
70
71
72
73
/*
Author: CNYALI_LK
LANG: C++
PROG: scon.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
const ll N=19,M=33333,K=14456789,p=1000000007;
ll ein[M],a[N][N],f[M],g[M],et[N][M],eto[K],_2t3[M];//g 指的就是刚才那个c
ll logs[M],p2[M];
int main(){
#ifdef cnyali_lk
freopen("scon.in","r",stdin);
freopen("scon.out","w",stdout);
#endif
ll n,m,t;
n=read(),m=read();t=1<<n;
for(ll i=1;i<=m;++i)a[read()-1][read()-1]=1;
for(ll i=0;i<n;++i)logs[1<<i]=i;
for(ll i=0;i<n;++i)for(ll j=1;j<t;++j){
et[i][j]=et[i][j^(j&(-j))]+a[i][logs[j&(-j)]];
}
p2[0]=1;
for(ll i=1;i<t;++i){_2t3[i]=_2t3[i>>1]*3+(i&1);p2[i]=p2[i-1]*2%p;}
for(ll i=1;i<t;++i){
for(ll j=0;j<n;++j)if(i&(1<<j))ein[i]+=et[j][i];
// printf("%lld\n",ein[i]);
}
for(ll i=1;i<t;++i)for(ll j=(t-1)^i;j;j=(j-1)&((t-1)^i)){
eto[_2t3[i]+_2t3[j]+_2t3[j]]=eto[_2t3[i^(i&(-i))]+_2t3[j]+_2t3[j]]+et[logs[i&(-i)]][j];
}
for(ll i=1;i<t;++i){
ll ka=i&(-i),kb=i^ka;
g[i]=0;
for(ll j=kb;j;j=(j-1)&kb){
g[i]=(g[i]-g[j]*f[i-j]%p+p)%p;
}
f[i]=p2[ein[i]];
for(ll j=i;j;j=(j-1)&i){
f[i]=(f[i]-g[j]*p2[ein[i-j]+eto[_2t3[i-j]+2*_2t3[j]]]%p+p)%p;
}
g[i]=(g[i]+f[i])%p;
}
printf("%lld\n",f[t-1]);
return 0;
}
# 容斥
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×