I 杰哥再找对象

题解

我们可以通过枚举结点 $1$ 和结点 $n$ 所在的连通块中结点的个数计算，设答案为 $a_{n}$ ，则：

a_n=\begin{cases} \displaystyle\sum\limits_{k=2}^{n}\left({n-2 \choose k-2}b_{k}c_{n-k}\right) & \text {$n\geq 2$} \\ 1 & \text {$n=1$} \end{cases}

解释： $a_{n}$ 表示 $1$ 与 $n$ 连通的带标号的无向图的个数。 $b_{n}$ 表示 $n$ 个带标号的点的无向连通图的个数。 $c_{n}$ 表示 $n$ 个带标号的点的无向图的个数。上式可以理解为，枚举 $1$ 与 $n$ 所在连通块的结点数 $k$ ，这 $k$ 个结点中有两个分别是 $1$ 和 $n$ ，因此需要在剩下的 $n - 2$ 个结点里选取 $k - 2$ 个结点，共 ${n-2 \choose k-2}$ 种方案，然后这 $k$ 个结点需要连通，共有 $b_{k}$ 种方案，剩下的 $n - k$ 个结点不影响答案，因此就是 $n - k$ 个带标号的结点的无向图的个数，共 $c_{n-k}$ 个，再根据乘法原理和加法原理即可得到上式。

令 $b_{0} = b_{1} = 0$ ，那么 $k$ 就能从 $0$ 开始，再将组合数展开，得：

a_n=\sum\limits_{k=0}^{n}\frac{(n-2)!}{(k-2)!(n-k)!}b_kc_{n-k}=(n-2)!\sum\limits_{k=0}^{\infty}\frac{b_k}{(k-2)!}\frac{c_{n-k}}{(n-k)!} \text {$\ \ \ (n\geq 2)$}

我们可以发现求和的每一项同时含有 $k$ 和 $n - k$ 。这个形式明显是两个多项式的卷积，因此，我们只需要把序列 $\frac{b_n}{(n-2)!}$ 和序列 $\frac{c_n}{n!}$ 计算出来之后，再求卷积，最后乘 $(n - 2)!$ 即可得到答案。

现在问题变成了求解序列 $b_{n}$ 和序列 $c_{n}$ ，即 $n$ 个带标号的点的无向连通图的个数和无向图的个数。我们知道 $n$ 个点的完全图存在 $\frac{n(n-1)}{2}$ 条边，对于每一条边，取或不取，对无向图的个数都有贡献，故 $c_n=2^{\frac{n(n-1)}{2}}$ 。

接下来求解 $b_{n}$ ：

我们利用指数生成函数。

令：

B(x)=\sum\limits_{n=0}^{\infty}b_n\frac{x^n}{n!}，C(x)=\sum\limits_{n=0}^{\infty}c_n\frac{x^n}{n!}

求导得：

B'(x)=\sum\limits_{n=0}^{\infty}b_{n+1}\frac{x^n}{n!}， C'(x)=\sum\limits_{n=0}^{\infty}c_{n+1}\frac{x^n}{n!}

这四个函数之后会用到。

思考无向连通图与无向图的关系，和上面类似，可以枚举结点 $1$ 所在的连通块的结点数 $k$ ，可得：

c_n=\sum\limits_{k=1}^{n}{n-1 \choose k-1}b_kc_{n-k}=\sum\limits_{k=0}^{n-1}{n-1 \choose k}b_{k+1}c_{n-k-1}

解释：计算 $n$ 个带标号的结点的无向图个数，可以枚举与结点 $1$ 所在连通块的结点数 $k$ ，这 $k$ 个结点中有一个是结点 $1$ ，因此，需要在剩下的 $n - 1$ 个结点选择 $k - 1$ 个结点，共有 ${n-1 \choose k-1}$ 种方案，这 $k$ 个结点需要连通，共 $b_{k}$ 种方案，剩下的 $n - k$ 个结点不影响答案，就是 $n - k$ 个带标号的结点的无向图的个数，共 $c_{n-k}$ 个，在根据乘法原理和加法原理得到上式。

还是将组合数展开，得：

c_n=\sum\limits_{k=0}^{n-1}\frac{(n-1)!}{k!(n-k-1)!}b_{k+1}c_{n-k-1}=(n-1)!\sum\limits_{k=0}^{n-1}\frac{b_{k+1}}{k!}\frac{c_{n-k-1}}{(n-k-1)!}

两边同时除以的 $(n - 1)!$ ，再乘 $x^{n-1}$ ，得：

\frac{c_n}{(n-1)!}x^{n-1}=\sum\limits_{k=0}^{n-1}(\frac{b_{k+1}}{k!}x^k)(\frac{c_{n-k-1}}{(n-k-1)!}x^{n-k-1})

将前四个函数带入上式，解微分方程：

\begin{aligned} C'(x)=&B'(x)C(x) \\ \frac{{\rm d}C(x)}{{\rm d}x}=&B'(x)C(x) \\ \frac{{\rm d}C(x)}{C(x)}=&B'(x){\rm d}x \\ \int\frac{{\rm d}C(x)}{C(x)}=&\int B'(x){\rm d}x \\ \because C(x)>&0\\ \therefore \ln C(x)=&B(x)+D \\ \because B(0)=&b_0=0\\ C(0)=&c_0=1 \\ \therefore D=&0 \\ \therefore B(x)=&\ln C(x) \end{aligned}

这样将 $C (x)$ 求对数即可得到 $B (x)$ ，自然就得到了 $b_{n}$ 。这道题就完成了。

$\mathcal O(n)$ 预处理 $1$ 到 $1 0^{5}$ 的阶乘、逆元和阶乘的逆元， $\mathcal O(n\log n)$ 计算 $c_{n}$ ， $\mathcal O(n)$ 得到 $C (x)$ ， $\mathcal O(n\log n)$ 求对数计算 $B (x)$ ， $O (n)$ 计算 $b_{n}$ ，再 $\mathcal O(n\log n)$ 计算卷积得到 $1$ 到 $1 0^{5}$ 的所有答案， $O (1)$ 输出答案，总时间复杂度 $\mathcal O(T+n\log n)$ 。

std:

#include <bits/stdc++.h>
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define endl "\n"
using namespace std;
typedef long long ll ;
typedef unsigned long long ull ;
const int mod97=1e9+7, mod33=998244353, mod99=1e9+9;
const int MAX=2e5+10, inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int drc[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const ll P[5]={mod33, (5LL<<25)+1, (17LL<<27)+1, (7LL<<52)+1, (29LL<<57)+1};
const int NUM=22;
const double PI = acos(-1.0);
const double eps = 1e-7;


int n;
ll wn[NUM];
ll fac[MAX>>1], inv[MAX>>1], inv_f[MAX>>1];
ll A[MAX<<1], B[MAX<<1];
ll ans[MAX<<1];
ull Pow(ull a,ull n,ull mod){
    ull ans = 1;
    while(n){
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
void Get_Wn(){
    int t = 1;
    for(int i = 0; i < NUM; ++i){
        wn[i] = Pow(3, (mod33 - 1) / t, mod33);
        t <<= 1;
    }
}
void Rader(ll a[], int len){
    int j = len >> 1;
    for(int i = 1; i < len - 1; ++i) {
        if(i < j) swap(a[i], a[j]);
        int k = len >> 1;
        while(j >= k) {
            j -= k;
            k >>= 1;
        }
        if(j < k) j += k;
    }
}
void NTT(ll a[], int len, int on) {
    Rader(a, len);
    int id = 0;
    for(int h = 2; h <= len; h <<= 1) {
        id++;
        for(int j = 0; j < len; j += h){
            ll w = 1;
            int up = j + (h >> 1);
            for(int k = j; k < up; ++k) {
                int kk = k + (h >> 1);
                ll u = a[k];
                ll t = w * a[kk] % mod33;
                a[k ] = u + t; if(a[k ] >= mod33) a[k ] = a[k ] - mod33;
                a[kk] = u - t; if(a[kk] <    0 ) a[kk] = a[kk] + mod33;
                w = w * wn[id] % mod33;
            }
        }
    }
    if(on == -1){
        int up = len >> 1;
        for(int i = 1; i < up; ++i)
            swap(a[i], a[len - i]);
        int Inv = Pow(len, mod33 - 2, mod33);
        for(int i = 0; i < len; ++i)
            a[i] = a[i] * Inv % mod33;
    }
}
void PolyInv(const ll a[], int n, ll b[])  {
    if(n == 1) { b[0] = Pow(a[0], mod33 - 2, mod33); return ; }
    int up = (n + 1) >> 1;
    PolyInv(a, up, b);
    int lim = 1; while(lim < (n << 1)) lim <<= 1;
    ll *c= new ll[lim]{};
    memcpy(c, a, n * sizeof(ll));
    memset(b + n, 0, (lim - n) * sizeof(ll));
    NTT(c, lim, 1), NTT(b, lim, 1);
    for(int i = 0; i < lim; ++i) {
        b[i] = (2LL - c[i] * b[i]) % mod33 * b[i] % mod33;
        if(b[i] < 0) b[i] += mod33;
    }
    NTT(b, lim, -1);
    memset(b + n, 0, (lim - n) * sizeof(ll));
    delete [] c;
}
void PolyLn(const ll a[], int n, ll b[]){
    int lim = 1; while(lim <= (n << 1)) lim <<= 1;
    ll *aa= new ll[lim]{}, *c= new ll[lim]{};
    for(int i = 1; i < n; ++i) aa[i-1] = a[i] * i % mod33;
    PolyInv(a, n, c);
    NTT(aa, lim, 1), NTT(c, lim, 1);
    for(int i = 0; i < lim; ++i) b[i] = aa[i] * c[i] % mod33;
    NTT(b, lim, -1);
    for(int i = n - 1; i; --i) b[i] = b[i-1] * inv[i] % mod33;
    memset(b + n, 0, (lim - n) * sizeof(ll)); b[0] = 0;
    delete []aa, delete []c;
}
void Conv(const ll a[], const ll b[], int n, ll c[])  {
    ll *ta= new ll[n], *tb= new ll[n];
    for(int i = 0; i < n; ++i) ta[i] = a[i], tb[i] = b[i];
    NTT(ta, n, 1);
    NTT(tb, n, 1);
    for(int i = 0; i < n; ++i)
        c[i] = ta[i] * tb[i] % mod33;
    NTT(c, n, -1);
    delete []ta, delete []tb;
}
void GetFac_Inv(){
	fac[0]=inv[1]=1;
	for(int i=1; i<=100000; ++i) fac[i] = fac[i-1] * i % mod33; // 阶乘
	inv_f[100000] = Pow(fac[100000], mod33-2, mod33);
	for(int i=99999; ~i; --i) inv_f[i] = inv_f[i+1] * (i+1) % mod33; // 阶乘的逆元
	for(int i=2; i<=100000; ++i) inv[i] = mod33 - mod33 / i * inv[mod33%i] % mod33; // 逆元
}
void Init(){
	Get_Wn();
	GetFac_Inv();
	for(int i=0; i<=100000; ++i){
		A[i] = Pow(2, (1LL * i * (i-1) >> 1) % (mod33-1), mod33) * inv_f[i] % mod33;
        // 代码写的是 a[n]，其实是题解中的 c[n]/n!
	}
	PolyLn(A, 100001, B); // B(x) ≡ ln(C(x)) (mod x^n)

	B[0] = B[1] = 0; // 别忘记 b[0] = b[1] = 0
    // 下面两个是求解 a[n] 的表达式中的 b[n]/(n-2)! 和 c[n]/n!
	for(int i=2; i<=100000; ++i){
		B[i] = B[i] * fac[i] % mod33 * inv_f[i-2] % mod33;
	}
	for(int i=0; i<=100000; ++i){
		A[i] = Pow(2, (1LL * i* (i-1) >> 1) % (mod33-1), mod33) * inv_f[i] % mod33;
	}
	int lim = 1; while(lim <= 200000) lim <<= 1;
	Conv(A, B, lim, ans); // 求卷积存入 ans[n]
	ans[1] = 1; // 依题意，ans[1] = 1
	for(int i=2; i<=100000; ++i) ans[i] = ans[i] * fac[i-2] % mod33; // 别忘记最后乘 (n-2)!
}
int main(){
	Init(); // 预处理所有答案
	int t ;
	cin >> t;
	while(t--){
		cin >> n;
cout << ans[n] << endl;
	}
	return 0;
}

题解 | # I 杰哥再找对象#

I 杰哥再找对象

题解

std: