讲题人：“这是一个很经典的模型，大家应该都会”
我：“???”
# 题面
给出 \(m\)，求所有 \(m\) 个点的有标号强联通竞赛图的哈密顿回路数量的平均数。答案对 \(998244353\) 取模。
输入 \(n\)，对每个 \(m=1\sim n\) 求解。
数据规模：\(n\le10^5\)。
# 解析
问题分成两个部分：
所有 \(m\) 个点的竞赛图的哈密顿回路数量；注意到只有强联通的竞赛图有哈密顿回路，所以计算时不用管强联通;
\(m\) 个点的强联通竞赛图数量。
第一个部分。我们发现对一个竞赛图计算它的哈密顿回路没法做，考虑对一个哈密顿回路计算它出现在多少个竞赛图中。
哈密顿回路从 \(1\) 处断开，就是一个从 \(1\) 开头的 \(1\sim m\) 的排列，数量为 \((m-1)!\)。我们钦定这样一条哈密顿回路在竞赛图上，相当于已经给 \(m\) 条边钦定了方向，剩下的 \(\frac{m(m-1)}2-m\) 条边随便定向，即哈密顿回路总数为：
\[2^{\frac{m(m-1)}{2}-m}\times(m-1)!
\]
特判一下 \(n\le2\)。
第二个部分。记 \(f_i\) 表示 \(i\) 个点的强联通竞赛图的数量，我们要计算 \(f_1\sim f_n\)。计算这些值，可以考虑生成函数 —— 注意到有标号，记 \(f_i\) 的 EGF 为 \(F(x)\)。
直接限制强联通并不好算，于是正难则反。计算一定没有强联通的竞赛图的数量。
重要性质
将竞赛图强联通缩点后的图记为 \(T\)，对 \(T\) 做拓扑排序，则按拓扑序排列的点在 \(T\) 上形成一条链。
如果竞赛图不是强联通，则一定存在多个强联通分量，结合上述性质，可以找到拓扑序最小的一个强联通分量 \(G_1\)，而剩下的图 \(G_2\) 是一个任意的竞赛图。由于 \(G_1\) 是极大的强联通分量，且拓扑序最小，则 \(G_1\) 和 \(G_2\) 之间的所有边都是从 \(G_1\) 连向 \(G_2\)。
我们可以枚举 \(G_1\) 的大小为 \(i\)，则 \(G_1\) 是大小为 \(i\) 的强联通竞赛图，而 \(G_2\) 为大小为 \(m-i\) 的任意竞赛图。记 \(g_i\) 为 \(i\) 个点的任意竞赛图数量。可以写出转移式：
\[f_s=g_s-\sum_{i=1}^{s-1}\binom{s}{i}f_ig_{s-i}
\]
有组合数，能够拆成 EGF 的形式。记 \(G(x)\) 为 \(g_i\) 的 EGF：
\[\begin{aligned}
\frac{f_s}{s!}=\frac{g_s}{s!}-\sum_{i=1}^{s-1}\frac{f_i}{i!}\times\frac{g_{s-i}}{(s-i)!}\\
F(x)=G(x)-F(x)G(x)
\end{aligned}
\]
分治 NTT 或者多项式求逆，但是感觉多项式求逆好写些……
# 源代码
/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 998244353, N = 1e5 + 10, L = 262144;
#define con(typ) const typ &
inline int add(int a, con(int) b) {
return (a += b) >= MOD ? a - MOD : a;
}
inline int sub(int a, con(int) b) {
return (a -= b) < 0 ? a + MOD : a;
}
inline int mul(con(int) a, con(int) b) {
return int(1ll * a * b % MOD);
}
inline int iPow(int a, int b) {
int r = 1;
while ( b ) {
if ( b & 1 ) r = mul(a, r);
a = mul(a, a), b >>= 1;
}
return r;
}
namespace BASICPOLY {
int rev[L + 10], elg2[L + 10], powg[L + 10];
void init() {
elg2[1] = 0, powg[0] = 1, powg[1] = iPow(3, (MOD - 1) >> 18);
for (int i = 2; i <= L; i++) {
elg2[i] = elg2[(i + 1) >> 1] + 1;
powg[i] = mul(powg[i - 1], powg[1]);
}
}
void ntt(int *arr, con(int) len, con(int) typ) {
for (int i = 1; i < len; i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
if ( i < rev[i] ) swap(arr[i], arr[rev[i]]);
}
for (int i = 1, ii = 2; i < len; i <<= 1, ii <<= 1) {
int s = L >> elg2[ii];
for (int j = 0; j < len; j += ii) {
int *a = arr + j, *b = a + i, *p = powg, q = *b;
for (int k = 0; k < i; k++, a++, q = mul(*(p += s), *(++b)))
*b = sub(*a, q), *a = add(*a, q);
}
}
if ( typ == -1 ) {
reverse(arr + 1, arr + len);
int ivn = MOD - ((MOD - 1) >> elg2[len]);
if ( mul(ivn, len) != 1 ) printf("???");
for (int i = 0; i < len; i++) arr[i] = mul(arr[i], ivn);
}
}
int ta[L + 10], tb[L + 10];
void polyMul(int *a, int *b, con(int) la, con(int) lb, int *r,
con(int) fr = -1) {
int lr = la + lb - 1, len = 1 << elg2[lr];
for (int i = 0; i < la; i++) ta[i] = a[i];
for (int i = la; i < len; i++) ta[i] = 0;
for (int i = 0; i < lb; i++) tb[i] = b[i];
for (int i = lb; i < len; i++) tb[i] = 0;
ntt(ta, len, 1), ntt(tb, len, 1);
for (int i = 0; i < len; i++) ta[i] = mul(ta[i], tb[i]);
ntt(ta, len, -1);
for (int i = 0, ii = ~fr ? fr : lr; i < ii; i++) r[i] = ta[i];
}
void polyInv(int *a, int *r, con(int) len) {
if ( len == 1 ) {
r[0] = iPow(a[0], MOD - 2);
return;
}
polyInv(a, r, (len + 1) >> 1);
int llen = 1 << elg2[len << 1];
for (int i = 0; i < len; i++) ta[i] = a[i];
for (int i = len; i < llen; i++) ta[i] = 0;
for (int i = 0, ii = (len + 1) >> 1; i < ii; i++) tb[i] = r[i];
for (int i = (len + 1) >> 1; i < llen; i++) tb[i] = 0;
ntt(ta, llen, 1), ntt(tb, llen, 1);
for (int i = 0; i < llen; i++)
ta[i] = mul(tb[i], sub(2, mul(ta[i], tb[i])));
ntt(ta, llen, -1);
for (int i = 0; i < len; i++) r[i] = ta[i];
}
}
int fac[N], ifac[N], ara[N], arb[N];
int calc(con(int) n) {
if ( n <= 2 ) return n == 1;
return mul(fac[n - 1], iPow(2, (n * (n - 1ll) / 2 - n) % (MOD - 1)));
}
int funS(con(int) n) {
return iPow(2, n * (n - 1ll) / 2 % (MOD - 1));
}
void init() {
fac[0] = 1;
for (int i = 1; i < N; i++)
fac[i] = mul(fac[i - 1], i);
ifac[N - 1] = iPow(fac[N - 1], MOD - 2);
for (int i = N - 2; ~i; i--)
ifac[i] = mul(ifac[i + 1], i + 1);
BASICPOLY::init();
for (int i = 1; i < N; i++) ara[i] = mul(funS(i), ifac[i]);
ara[0]++;
BASICPOLY::polyInv(ara, arb, N);
ara[0]--;
BASICPOLY::polyMul(ara, arb, N, N, ara, N);
for (int i = 1; i < N; i++) ara[i] = mul(ara[i], fac[i]);
}
int main() {
init();
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
if ( ara[i] )
printf("%d\n", mul(calc(i), iPow(ara[i], MOD - 2)));
else printf("-1\n");
}
return 0;
}
THE END
Thanks for reading!
你喜欢海风咸咸的气息
踩着湿湿的沙砾
你说人们的骨灰应该撒进海里
你问我死后会去哪里
有没有人爱你
世界能否不再
——《海底(Cover)》 By 祖娅纳惜
