#C241019A. 拓扑序计数
标签（Label）
- 状态压缩
- 动态规划
网址（Website）
题解（Solution）
算法分析
设 $f(S)$ 表示按照拓扑序从前往后的顺序加点，初始为空集，到已经加入 $S$ 这个点集，这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点，初始为全集，到现在还剩下 $S$ 这个点集，此时删除顺序的方案数。$f, g$ 都可以在 $O(2^n n)$ 时间内简单地 $dp$ 求出。
对于给定的 $u, v$，$u$ 在 $v$ 前，就是要，拓扑序加入 $v$ 那一刻，$u$ 已经在拓扑序里了。所以，
$ans_{u,v} = \sum_{[u \in S, v \notin S]} f(S) g(S \cup {v})$（枚举加入 $v$ 之前一刻，有哪些点加入了拓扑序）
直接实现该算法的时间复杂度为 $O(2^n n^2)$，但 $S$ 的枚举有 $1/4$ 的常数，已经可以过。
当然，上述算法还可以继续优化到 $O(2^n n)$：枚举 $S, v$，相当于 $\forall u \in S$，$ans_{u,v}$ 都加上一个定值。
因此瓶颈在于：
“给出 $a_0 \sim a_{2^n - 1}$，对所有 $u$ 求出 $\sum_{u \in S} a_S$”。可以用下面的方法：
for i from n-1 downto 0:
for j from 2^i to (2^{i+1}-1):
ans[i]+=a[j]
a[j-2^i]+=a[j]最后 $ans_u$ 就是答案。因此我们把 $O(2^n n)$ 的循环优化到了 $O(2^n)$。（但是实际上速度仅仅变快了不到一倍）
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 21;
const int S = (1<<20);
const int B = sizeof(int);
bool ST;
int f[S],g[S],c[N][S],ans[N][N];
int n,m,inn[N],out[N];
void clear(){
memset(f,0,(1<<n)<<3),
memset(g,0,(1<<n)<<3);
For(i,0,n-1){
memset(ans[i],0,n<<3);
memset(c[i],0,(1<<n)<<3);
inn[i] = out[i] = 0;
}
}
void Solve(){
n = rd(), m = rd();
For(i,1,m){
int x = rd()-1, y = rd()-1;//注意：这个地方把点的范围缩到了[0,n-1]
out[x] |= 1<<y,
inn[y] |= 1<<x;
}
g[(1<<n)-1] = 1;
Rof(s,(1<<n)-1,0) if(g[s]){//如果有当前这个状态
For(i,0,n-1) if((s>>i&1) && (out[i] & ~s) == out[i]){
g[s - (1<<i)] += g[s];
}
}
f[0] = 1;
For(s,0,(1<<n)-1) if(f[s]){
For(i,0,n-1) if(!(s>>i&1) && (inn[i] & s) == inn[i]){
f[s + (1<<i)] += f[s];
c[i][s] += f[s] * g[s|1<<i];
}
}
For(i,0,n-1) Rof(s,(1<<n)-1,1){
int x = __lg(s);
ans[i][x] += c[i][s];
c[i][s-(1<<x)]+=c[i][s];
}
For(i,0,n-1) For(j,0,n-1) cout << ans[i][j] << " \n"[j == n - 1];
clear();
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("topo.in","r",stdin);
freopen("topo.out","w",stdout);
int T = rd(), Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
