[Medium-Hard] P6295 有标号 DAG 计数

xiezheyuan2025/5/3约 1080 字大约 5 分钟

简要题意

令 $f(n)$ 表示 $n$ 个点的弱连通 DAG 数量。给定 $T$ ，输出 $f(1)\bmod p,f(2)\bmod p,\cdots,f(T)\bmod p$ 。其中 $p=998,244,353$ 。

$1\leq T\leq 10^5$ 。称一个有向图是弱连通的，当且仅当将所有有向边替换为无向边后的图连通。

思路

令 $\hat{\mathbf{F}}(z)=\sum_{i\geq 0}\frac{f(i)}{i!}z^i$ ， $g(n)$ 表示 $n$ 个点的 DAG 数量， $\mathbf{G}(z)=\sum_{i\geq 0}g(i)z^i,\hat{\mathbf{G}}(z)=\sum_{i\geq 0}\frac{g(i)}{i!}z^i$ 。

则根据多项式 $\exp$ 的组合意义有 $\exp(\hat{\mathbf{F}}(z))=\hat{\mathbf{G}}(z)$ ，即 $\hat{\mathbf{F}}(z)=\ln \hat{\mathbf{G}}(z)$ 。故只要快速求出 $g(n)$ 就可以快速求出 $f(n)$ 。

考虑如何求出 $g(n)$ ，有一个 naive 的 dp：

g(n)=\sum_{i=1}^{n}\binom{n}{i}g(n-i)2^{i(n-i)}

大意是枚举入度为 $0$ 的点有 $i$ 个，这样的选法有 $\binom{n}{i}$ 种，剩余的 DAG 有 $g(n-i)$ 种方案，入度为 $0$ 的点 $i$ 连向其余点的边有 $2^{i(n-i)}$ 种选法。但是这样有一定问题，就是剩余点中，如果有若干点是剩余 DAG 的入度为 $0$ 点，且与原 DAG 的入度为 $0$ 的点没有边相连，那么这一部分会算重。换句话说， $i$ 不能保证恰好，只能保证至少。

遇到这种困境，不妨容斥，也就是需要找到容斥系数函数 $\epsilon(x)$ 使得对于任意 $S$ 有 $\sum_{T\subseteq S,T\neq\varnothing} \epsilon(|T|)$ ，可以发现 $\epsilon(x)=(-1)^{x+1}$ 就满足条件。因此可以得到一个正确的 dp：

g(n)=\sum_{i=1}^{n}\binom{n}{i}g(n-i)(-1)^{i+1}2^{i(n-i)}

直接转移，时间复杂度 $O(T^2)$ 难以接受，不过这个形式如果没有 $2^{i(n-i)}$ 的话很像卷积，因此尝试对 $2^{i(n-i)}$ 变形。

注意到下面的恒等式：

$nm=\binom{n+m}{2}-\binom{n}{2}-\binom{m}{2}$

证明是平凡的。

根据这个恒等式，我们对原式变形：

\begin{aligned} &g(n)=\sum_{i=1}^{n}\binom{n}{i}(-1)^{i+1}\cdot g(n-i)\cdot \frac{2^{\binom{n}{2}}}{2^{\binom{i}{2}2^{\binom{n-i}{2}}}}\\ &\frac{g(n)}{n!\cdot 2^{\binom{n}{2}}}=\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i!\cdot 2^{\binom{i}{2}}}\cdot \frac{g(n-i)}{2^{\binom{n-i}{2}}\cdot (n-i)!} \end{aligned}

得到了标准卷积形式。不妨记 $p(n)=\frac{g(n)}{n!\cdot 2^{\binom{n}{2}}},q(n)=\frac{(-1)^{n+1}}{n!\cdot 2^{\binom{n}{2}}},\mathbf{P}(z)=\sum_{i\geq 0}p(i)z^i,\mathbf{Q}(z)=\sum_{i\geq 1}q(i)z^i$ ，则得到：

p(n)=\sum_{i=1}^{n}q(i)p(n-i)\implies \mathbf{P}(z)=\mathbf{P}(z)\mathbf{Q}(z)+1

注意那个 $+1$ ，由于 $\mathbf{P}(0)=1,\mathbf{Q}(0)=0$ ，所以 $[z^0](\mathbf{P}(z)\cdot \mathbf{Q}(z))=1$ ，故要补上一个 $1$ 来修正常数项。

解得 $\mathbf{P}(z)=\frac{1}{1-\mathbf{Q}(z)}$ 。而 $q(n)$ 是易求的，故只要做一遍多项式求逆，然后做一遍多项式对数函数，就可以求出答案。

时间复杂度 $O(T\log T)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x,x)){
        if(y & 1) ret = Mul(ret, x);
    }
    return ret;
}

int Inv(int x){ return fastpow(x, mod-2); }

namespace poly {
    // ... poly template ...
}

using poly::Poly;

const int N = 1e5 + 5;
int n, fact[N];

int magic(int i){
    return fastpow(2, ((1ll * i * (i - 1)) >> 1) % (mod - 1));
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n, fact[0] = 1;
    for(int i=1;i<=n;i++) fact[i] = Mul(fact[i - 1], i);
    Poly Q(n + 1);
    for(int i=1;i<=n;i++){
        Q[i] = Inv(Mul(fact[i], magic(i)));
        if(!(i & 1)) Q[i] = Sub(0, Q[i]);
    }
    Poly P = ~(1 - Q), G(n + 1);
    for(int i=0;i<=n;i++) G[i] = Mul(P[i], magic(i));
    Poly F = G.ln();
    for(int i=1;i<=n;i++) cout << Mul(F[i], fact[i]) << '\n';
    return 0;
}

// Written by xiezheyuan

[Medium-Hard] P6295 有标号 DAG 计数

简要题意

思路

代码

附注