P11714 题解

· · 题解

其实是整合了多篇题解的长处，这有人看不懂我直接吃。

Sol

发现强连通很难刻画，不妨使用单步容斥，转化成算非强连通方案数。

考虑刻画一下非强连通，发现缩点之后一定是一个点数大于 1 的 DAG。

于是，呃，考虑一种比较劣的做法，就是先暴力枚举这个图缩点之后每个点属于的 SCC 是哪个，然后对着这个算方案数。

于是现在需要算 DAG 生成子图。

考虑刻画 DAG，发现其一定存在一些点入度为 0。把这些点删了之后剩下的点还是 DAG，于是找到了一个子结构，可以对着这个 DP。

设 dp_S 表示 S 的答案，E_{S,T} 表示 S 到 T 的边数，则有：

dp_S=\sum_{T\subseteq S,T\neq \emptyset}dp_{S-T}2^{E_{T,S-T}}

但是这对吗？这不对。因为 S-T 里面可能还有入度为 0 的点，会导致算重。

考虑一下子集反演，当前全集为 S，设 f_T 表示 T 内点恰为所有入度为 0 的点的方案数，g_T 表示钦定 T 内点入度为 0 的方案数。显然 g_T=dp_{S-T}2^{E_{T,S-T}}。有关系式：

g_T=\sum_{T\subseteq R}f_R

反演得到：

f_T=\sum_{T\subseteq R}(-1)^{|R|-|T|}g_R

重写一下转移式，进行一些式子的推导：

dp_S&=\sum_{T\subseteq S,T\neq \emptyset}f_T\\ &=\sum_{T\subseteq S,T\neq \emptyset}\sum_{T\subseteq R}(-1)^{|R|-|T|}g_R\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|}g_R\sum_{T\subseteq R,T\neq \emptyset}(-1)^{|T|}\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|}g_R([R=\emptyset]-1)\\ &=\sum_{R\subseteq S,R\neq \emptyset}(-1)^{|R|+1}g_R\\ &=\sum_{T\subseteq S,T\neq \emptyset}(-1)^{|T|+1}dp_{S-T}2^{E_{T,S-T}} \end{aligned}

于是得到了一个 O(3^n) 算一次的做法，但是乘上暴力枚举缩点方案数之后复杂度爆炸。

考虑拓展这个东西到非强连通图计数上。

设 dp_S 表示 S 的答案，即 S 缩成一个点的方案数。仿照上面的方法，设 g_T 表示 T 内的点缩成若干个入度为 0 的点的方案数，转移的时候枚举 T，钦定 T 内点缩成了若干入度为 0 的点：

dp_{S}=2^{E_{S,S}}-\sum_{T\subseteq S,T\neq \emptyset}(-1)^{?}g_T2^{E_{T,S-T}+E_{S-T,S-T}}

但是发现容斥系数是不确定的，因为并不知道 T 内的点到底缩成了多少个点。于是考虑修改 g_T 的定义，令其包含上容斥系数，即缩成奇数个点的方案数减去缩成偶数个点的方案数，再写：

dp_{S}=2^{E_{S,S}}-\sum_{T\subseteq S,T\neq \emptyset}g_T2^{E_{T,S-T}+E_{S-T,S-T}}

这个式子可以 O(3^n) 做了。但是还没做完，还需要算 g_S。

考虑找子结构，发现这些缩完之后的点互不相干，于是可以钦定 \operatorname{lowbit}(S) 所属的 SCC 是新加入的：

g_S=dp_S-\sum_{T\subset S,\operatorname{lowbit}(S)=\operatorname{lowbit}(T)}dp_Tg_{S-T}

第一项是考虑 S 单独为一个 SCC，1 是奇数，所以要加上。后面一串是增加一个 SCC，奇偶性改变，所以要减去。

但是又出现了新问题，g_S 和 dp_S 好像互相依赖。真的互相依赖吗？dp_S 的转移式中只有 S=T 时会用到 g_S。重申一遍 dp_S 是 S 强连通的方案数，那么在 dp_S 中减去 g_S 中的 dp_S 时，减去的这个 dp_S 是合法的方案数，其不应该被减掉。

所以先算出 g_S，不加上 dp_S，再算出来 dp_S，把 dp_S 加到 g_S 上，是正确的。

于是现在只剩下最后一个问题了，怎么算 E_{S,T}。

看起来这个状态数是 4^n 的，但是观察发现对于每个 S，只需要用到形如 E_{T,S-T} 或者 E_{S,S} 形式的 E。T\subseteq S，所以状态数是 3^n。但是空间复杂度还是 O(4^n)，所以考虑每枚举一个 S 就重新计算 E_{T,S-T}，对于 E_{T,T} 另外开一个计算。

先预处理出 out_u 表示 u 连向的点集，in_u 表示连向 u 的点集，这样就有递推式：

E_{S,S}=E_{S-x,S-x}+\operatorname{popcount}(in_x\operatorname{and}S)+\operatorname{popcount}(out_x\operatorname{and}S)

这样，整个问题就能做到 O(3^n) 了，非常厉害。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=18,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,m,dp[1<<N],g[1<<N],in[N],out[N],e1[1<<N],e2[1<<N],p2[1145],pos[1<<N];
inline int lowbit(int x){return x&(-x);}
inline int popcnt(int x){return __builtin_popcount(x);}
vector<int> G[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    p2[0]=1;
    for(int i=1;i<=1000;i++)p2[i]=p2[i-1]*2%mod;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        out[u]|=(1<<(v-1));
        in[v]|=(1<<(u-1)); 
    }
    for(int i=0;i<n;i++)pos[1<<i]=i+1;
    for(int S=1;S<(1<<n);S++){
        int x=lowbit(S);
        e2[S]=e2[S-x]+popcnt(in[pos[x]]&S)+popcnt(out[pos[x]]&S);
    }
    for(int S=1;S<(1<<n);S++){
        e1[S]=0;
        for(int T=(S-1)&S;T;T=(T-1)&S){
            int x=lowbit(S-T);
            e1[T]=e1[T+x]-popcnt((S-T)&out[pos[x]])+popcnt(T&in[pos[x]]);
        }
        for(int T=(S-1)&S;T;T=(T-1)&S){
            if(lowbit(S)!=lowbit(T))continue;
            g[S]=(g[S]-dp[T]*g[S-T]%mod+mod)%mod;
        }
        dp[S]=p2[e2[S]];
        for(int T=S;T;T=(T-1)&S){
            dp[S]=(dp[S]-g[T]*p2[e1[T]+e2[S-T]]%mod+mod)%mod;
        }
        g[S]=(g[S]+dp[S])%mod;
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}