「清华集训2014-主旋律」题解

P11714 [清华集训 2014] 主旋律

pref

怎么新赛季就开始了。

一直想补岁月，但至今没有实现，也就只好先从主旋律下手。

我该在哪里停留？我问我自己。

sol

题意就是求删后原图仍强联通的有向边删边方案数。

强联通是不好刻画的，考虑非强联通。不难发现，其满足缩点之后是一个 DAG，先从 DAG 下手。

考虑刻画 DAG，不难想到拓扑，从而考虑到可以从入度为 \(0\) 的点入手，这些点删完之后得到的图仍然是 DAG，于是可以考虑从这里入手 DP。

令点集 \(S\) 的生成 DAG 方案数为 \(dp(S)\)，记 \(f(T)\) 表示 \(S\) 内有且仅有 \(T\) 点集中的点入度为 \(0\) 的方案数，则有转移：

\[dp(S)=\sum_{\varnothing\subsetneqq T\subseteq S} f(T) \]

容斥求 \(f\)，记 \(g(T)\) 为钦定 \(T\) 点集中的点入度为 \(0\) 的方案数，\(E_{S,T}\) 为 \(S\) 点集连向 \(T\) 点集的边数，显然有：

\[g(T)=2^{E_{T,S-T}}dp(S-T) \]

则有：

\[f(T)=\sum_{T\subseteq R\subseteq S}(-1)^{|R|-|T|}g(R) \]

计算 \(dp(S)\)：

\[\begin{aligned} dp(S)&=\sum_{\varnothing\subsetneqq T\subseteq S}\sum_{T\subseteq R\subseteq S}(-1)^{|R|-|T|}g(R)\\ &=\sum_{\varnothing\subsetneqq R\subseteq S}(-1)^{|R|}\sum_{\varnothing\subsetneqq T\subseteq R}(-1)^{|T|}g(R)\\ &=\sum_{\varnothing\subsetneqq R\subseteq S}(-1)^{|R|}(-[R=\varnothing])g(R)\\ &=\sum_{\varnothing\subsetneqq R\subseteq S}(-1)^{|R|+1}g(R)\\ &=\sum_{\varnothing\subsetneqq T\subseteq S}(-1)^{|T|+1}2^{E_{T,S-T}}dp(S-T) \end{aligned} \]

考虑拓展到缩点前的原图上，记 \(dp(S)\) 表示 \(S\) 是个 SCC 的方案数，\(g(T)\) 表示钦定 \(T\) 中点缩成若干入度为 \(0\) 的点的方案数，我们尝试仿照上面的式子写转移式，但不难发现容斥系数无法得到，其原因是无法得知 \(T\) 中的点到底缩成了几个入度为 \(0\) 的点。

考虑把容斥系数融入到 \(g\) 的定义中去，那么 \(g(S)\) 表示 \(S\) 中点缩成奇数个入度为 \(0\) 的点的方案数减去 \(S\) 中点缩成偶数个入度为 \(0\) 的点的方案数的值。在此之后求 \(g\) 其实也没有变得很困难，钦定一个子集视作新加入的来转移即可，强制令其包含 \(S\) 中某一个定点，比如 \(\mathrm{lowbit}(S)\) 代表元素，即可得到：

\[g(S)=dp(S)-\sum_{T\subset S\land \mathrm{lowbit}(S)=\mathrm{lowbit}(T)}dp(T)g(S-T) \]

也就是缩成一个 SCC 的方案数，减去新加 SCC 的方案数。后者是因为新加一个块块数奇偶性改变，相当于乘了一个容斥系数 \(-1\)。

得到 \(g\) 之后即可得到 \(dp\)：

\[dp(S)=2^{E(S,S)}-\sum_{T\subseteq S}2^{E_{T,S-T}+E_{S-T,S-T}}g(T) \]

特别的，当 \(S=T\) 时，\(g(S)\) 此时不应加上 \(dp(S)\)，考虑组合意义理解一下即可。那么就是先算 \(g(S)\) 不加上 \(dp(S)\)，再算得 \(dp(S)\)，最后给 \(g(S)\) 加回去即可。

然后压力给到 \(E\) 的计算，这个东西现在状态数 \(4^n\)，成为了瓶颈。然而不难发现，我们只会用到 \(E_{S,S},E_{T,S-T}\) 这两种形式的状态，故而状态数实际上只需要 \(3^n\)。考虑随 \(S\) 动态更新这两个东西，定义 \(I_v\) 为连向点 \(v\) 的点集，\(O_v\) 为点 \(v\) 连向的点集，每次钦定集合内一个点 \(u\)（比如 \(\mathrm{lowbit}\)）转移即可，有：

\[E_{S,S}=E_{S-u,S-u}+|I_u\cap S|+|O_u\cap S|\\ E_{T,S-T}=E_{T+u,S-T-u}-|O_u\cap(S-T)|+|I_u\cap T| \]

于是这个问题结束了。最后复杂度为 \(O(3^n)\)。

code

const int N=15,S=1<<N;int n,m;
int out[N],in[N],lg[S],e1[S],e2[S];
mint f[S],g[S],pt[N*N];inline void Main(){cin>>n>>m;pt[0]=1;rep(i,1,n*n)pt[i]=pt[i-1]*2;lg[1]=0;rep(i,2,1<<n-1)lg[i]=lg[i>>1]+1;rep(i,1,m){int a,b;cin>>a>>b;--a,--b;out[a]|=1<<b;in[b]|=1<<a;}repl(s,1,1<<n){int x=s&-s;e2[s]=e2[s^x]+__builtin_popcount(s&in[lg[x]])+__builtin_popcount(s&out[lg[x]]);}repl(s,1,1<<n){e1[s]=0;for(int t=s-1&s;t;t=t-1&s){int x=s-t&t-s;e1[t]=e1[t|x]-__builtin_popcount(s-t&out[lg[x]])+__builtin_popcount(t&in[lg[x]]);}for(int t=s-1&s;t;t=t-1&s){if((s&-s)!=(t&-t))continue;g[s]-=f[t]*g[s^t];}f[s]=pt[e2[s]];for(int t=s;t;t=t-1&s)f[s]-=g[t]*pt[e1[t]+e2[s^t]];g[s]+=f[s];}put(f[(1<<n)-1]);
}