题意
对 个点有标号的有向无环图进行计数,要求:弱连通图(所有的有向边替换为无向边后的图为连通图)。输出答案对
取模的结果。。
思路
设 表示 个点的弱连通 DAG 的个数, 表示 个点的 DAG 的个数。考虑枚举入度为 的点,将他们向剩下的点任意连边转移,有:
这个式子是错误的,因为会算重。对于一个入度为 的点集 ,在所有的集合 都会将这个算重。我们需要构造 满足 。显然可以构造 。然后这个式子就变为了不重不漏的式子:
指数上出现了二次的东西,很难进行后面的处理,但是有:
这个式子根据组合意义显然可证。那么 就可以化为:
我们将原式子拆开
设生成函数:
显然当 的时候我们 才有意义。但是卷积的下标是 开始的,我们不妨假设 。这样上面的式子就可以写成卷积的形式:
现在我们已经求得 。 接下来我们讨论 和 的关系。枚举其中一个固定点所在的弱连通 DAG 大小:
暴力展开后得到:
所以有:
两边积分可得:
一次多项式求逆 + 一次多项式 即可完成本题。时间复杂度 。
代码
#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;
}