发表于 | 分类于 | 0 | 阅读次数 1239

题意

对 nn 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。输出答案对
998244353998244353 取模的结果。1≤n≤1051 \le n \le 10^5。

思路

设 fif_i 表示 ii 个点的弱连通 DAG 的个数，gig_i 表示 ii 个点的 DAG 的个数。考虑枚举入度为 00 的点，将他们向剩下的点任意连边转移，有：

gi=∑j=1i(ij)gi−j×2j(i−j)g_i = \sum_{j=1}^i\binom{i}{j }g_{i-j}\times2^{j(i-j)}

这个式子是错误的，因为会算重。对于一个入度为 00 的点集 T\mathcal{T}，在所有的集合 S⊂T\mathcal{S} \subset \mathcal{T} 都会将这个算重。我们需要构造 F(T)F(\mathcal{T}) 满足 ∑S∈TF(S)=1\sum_{\mathcal{S} \in \mathcal{T}} F(\mathcal{S}) = 1。显然可以构造 F(S)=(−1)∣S∣+1F(\mathcal{S}) = (-1)^{|\mathcal{S}| + 1}。然后这个式子就变为了不重不漏的式子：

gi=∑j=1i(−1)j+1(ij)gi−j×2j(i−j)g_i = \sum_{j=1}^i(-1)^{j+1}\binom{i}{j}g_{i-j}\times2^{j(i-j)}

指数上出现了二次的东西，很难进行后面的处理，但是有：

j(i−j)=(i2)−(j2)−(i−j2)j(i-j) = \binom{i}{2} - \binom{j}{2} - \binom{i - j}{2}

这个式子根据组合意义显然可证。那么 2j(i−j)2^{j(i-j)} 就可以化为：

2(i2)2(j2)×2(i−j2)\frac{2^{\binom{i}{2}}}{2^{\binom{j}{2}} \times 2^{\binom{i-j}{2}}}

我们将原式子拆开

gi(i2)i!=∑j=1i(−1)j+12(j2)j!×gi−j2(i−j2)(i−j)!\frac{g_i}{\binom{i}{2}i!} = \sum_{j=1}^i\frac{(-1)^{j+1}}{2^{\binom{j}{2}}j!}\times\frac{g_{i-j}}{2^{\binom{i-j}{2}}(i-j)!}

设生成函数：

F^(x)=∑i≥0fixii!\hat F(x) = \sum_{i \ge 0} \frac{f_ix^i}{i!}

G^(x)=∑i≥0gixi(i2)i!\hat G(x) = \sum_{i \ge 0} \frac{g_ix^i}{\binom{i}{2}i!}

H^(x)=∑i≥0(−1)i+1xi2(i2)i!\hat H(x) = \sum_{i \ge 0}\frac{(-1)^{i+1}x^i}{2^{\binom{i}{2}}i!}

显然当 i>0i > 0 的时候我们 fi,gif_i,g_i 才有意义。但是卷积的下标是 00 开始的，我们不妨假设 g0=f0=1g_0 = f_0 = 1。这样上面的式子就可以写成卷积的形式：

G^(x)=G^(x)H^(x)+1⇒G^(x)=11−H^(x)\hat G(x) = \hat G(x)\hat H(x) + 1 \Rightarrow \hat G(x) = \frac{1}{1 - \hat H(x)}

现在我们已经求得 G^(x)\hat G(x)。 接下来我们讨论 F^(x)\hat F(x) 和 G^(x)\hat G(x) 的关系。枚举其中一个固定点所在的弱连通 DAG 大小：

gn=∑j≥0(n−1j−1)fjgn−jg_n = \sum_{j \ge 0}\binom{n-1}{j-1}f_jg_{n-j}

暴力展开后得到：

gn(n−1)!=∑i≥0fi(i−1)!×gn−i(n−i)!\frac{g_n}{(n-1)!} = \sum_{i\ge0} \frac{f_i}{(i-1)!}\times\frac{g_{n-i}}{(n-i)!}

所以有：

G^′(x)=F^′(x)G(x)⇒F^′(x)=G^′(x)G(x)\hat G'(x) = \hat F'(x)G(x) \Rightarrow \hat F'(x) = \frac{\hat G'(x)}{G(x)}

两边积分可得：

F^(x)=∫G^′(x)G(x)=ln⁡(G(x))\hat F(x) = \int \frac{\hat G'(x)}{G(x)} = \ln(G(x))

一次多项式求逆 + 一次多项式 ln⁡\ln 即可完成本题。时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1 << 20, mod = 998244353, gi = 3, gii = 332748118; 

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int limit, r[N];
ll a[N], b[N], c[N];

void NTT(ll* f, int type) {
	for(int i = 0; i < limit; i++)
		if (i < r[i])
			swap(f[i], f[r[i]]);
	for (int mid = 1; mid < limit; mid <<= 1) {
		ll W = qpow(type == 1 ? gi : gii, (mod - 1) / (mid << 1));
		for (int R = mid << 1, j = 0; j < limit; j += R) {
			ll w = 1;
			for (int k = 0; k < mid; k++, w = (w * W) % mod) {
				ll x = f[j + k], y = w * f[j + k + mid] % mod;
				f[j + k] = (x + y) % mod;
				f[j + mid + k] = (x - y + mod) % mod;
			}
		}
	}
	if (type == 1) return;
	ll inv = qpow(limit, mod - 2);
	for (int i = 0; i < limit; i++)
		f[i] = (f[i] * inv + mod) % mod;
	return;
}

void getinv(ll* f, ll* g, int n) {
    if (n == 1) {
        g[0] = qpow(f[0], mod - 2);
        return;
    }
    getinv(f, g, n + 1 >> 1);
    limit = 1;
	int l = 0;
	while (limit <= n + n) limit <<= 1, l++;
	assert(limit <= 4 * n);
	for (int i = 0; i < limit; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	for (int i = 0; i < n; i++) c[i] = f[i];
	for (int i = n; i < limit; i++) c[i] = 0;
	NTT(c, 1);
	NTT(g, 1);
	for (int i = 0; i < limit; i++)
		g[i] = ((2ll - g[i] * c[i] % mod) + mod) % mod * g[i] % mod;
	NTT(g, -1);
	for (int i = n; i < limit; i++) 
		g[i] = 0;
}

void derivation(ll* f, ll* g, int n) {
	g[n - 1] = 0;
	for (int i = 1; i < n; i++) g[i - 1] = i * f[i] % mod;
}

void integral(ll* f, ll* g, int n) {
	for (int i = 1; i < n; i++) g[i] = f[i - 1] * qpow(i, mod - 2) % mod;
	g[0] = 0;
}

void getln(ll* f, ll* g, int n) {
	derivation(f, a, n);
	getinv(f, b, n);
	limit = 1;
	int l = 0;
	while (limit <= n) limit <<= 1, l++;
 	for (int i = 0; i < limit; i++) 
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	NTT(a, 1);
	NTT(b, 1);
	for (int i = 0; i < limit; i++) a[i] = a[i] * b[i] % mod;
	NTT(a, -1);
	integral(a, g, n);
}

int n;
ll fac[N], inv[N], invfac[N];
ll G[N], F[N], invG[N];

int main() {
    cin >> n;
    n++;
    limit = 1;
    while (limit <= n + n) limit <<= 1;
    fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
    for (int i = 2; i <= limit; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;   
        invfac[i] = invfac[i -1] * inv[i] % mod;
    }
    for (int i = 1; i < n; i++) {
        G[i] = 1ll * qpow(qpow(2, 1ll * i * (i - 1) >> 1), mod - 2) * invfac[i] % mod;
        if (i & 1) G[i] = mod - G[i];
    }
    G[0] = 1;
    getinv(G, invG, n);
	memset(G, 0, sizeof G);
    for (int i = 0; i < n; i++) 
        G[i] = invG[i] * qpow(2, 1ll * i * (i - 1) >> 1) % mod;
    limit = 1;
    while (limit <= n) limit <<= 1;
    getln(G, F, limit);
    for (int i = 1; i < n; i++)
        cout << 1ll * fac[i] * F[i] % mod << endl;
    return 0;
}