专栏文章
P11714 题解
P11714题解参与者 6已保存评论 6
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mipk7g5e
- 此快照首次捕获于
- 2025/12/03 13:21 3 个月前
- 此快照最后确认于
- 2025/12/03 13:21 3 个月前
其实是整合了多篇题解的长处，这有人看不懂我直接吃。
Sol
发现强连通很难刻画，不妨使用单步容斥，转化成算非强连通方案数。
考虑刻画一下非强连通，发现缩点之后一定是一个点数大于 的 DAG。
于是，呃，考虑一种比较劣的做法，就是先暴力枚举这个图缩点之后每个点属于的 SCC 是哪个，然后对着这个算方案数。
于是现在需要算 DAG 生成子图。
考虑刻画 DAG，发现其一定存在一些点入度为 。把这些点删了之后剩下的点还是 DAG，于是找到了一个子结构，可以对着这个 DP。
设 表示 的答案， 表示 到 的边数，则有：
但是这对吗？这不对。因为 里面可能还有入度为 的点，会导致算重。
考虑一下子集反演，当前全集为 ，设 表示 内点恰为所有入度为 的点的方案数， 表示钦定 内点入度为 的方案数。显然 。有关系式：
反演得到：
重写一下转移式，进行一些式子的推导：
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_{T,S-T}=E_{T+x,S-T-x}-\operatorname{popcount}(out_x\operatorname{and} (S-T))+\operatorname{popcount}(in_x\operatorname{and} T)\\
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
```cpp
#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;
}
```相关推荐
评论
共 6 条评论，欢迎与作者交流。
正在加载评论...