「BZOJ 5093」图的价值 题解

---

组合数学学不明白祭.

• 题目链接: https://lydsy.com/JudgeOnline/problem.php?id=5093

根据题意列出式子, 并通过第二类 Stirling 数对式子进行化简, 在合适的时间内计算出结果.

前置知识

• NTT

• 第二类 Stirling 数的一些性质

  • $m^n=\sum_{i=0}^{m} \begin{Bmatrix}n \ i\end{Bmatrix} i! \cdot \binom{m}{i}$
    提供了一个计算自然数幂的新思路.

  • $\begin{Bmatrix} n\ m\end{Bmatrix} = \sum_{i=0}^{m} \frac{(-1)^i}{i!} \frac{(m-i)^n}{(m-i)!}$
    显然是一个卷积的形式, 可以在 $O(n \log n)$ 的时间复杂度计算.

    详尽的解释可以在这里找到: https://www.cnblogs.com/y2823774827y/p/10700231.html

题目思路

考虑单独枚举一个点的度数 $i$, 那么答案可以表示为

$$n \cdot \sum_{i=0}^{n-1} \binom{n-1}{i} i^k \cdot 2^{\frac{1}{2} (n-1)(n-2)}$$

如何理解呢? 首先, 每个点在枚举时是等价的, 所以最终结果乘 $n$

其次, 当前点的贡献为 $i^k$, 考虑度数为 $k$, 即在剩余的 $n-1$ 个点中选择 $i$ 个点. 要求无向图无重边, 剩余的边随意, 方案数为 $2^{\frac{1}{2} (n-1)(n-2)}$.

整理, 得

$$n \cdot 2^{\frac{1}{2} (n-1)(n-2)} \sum_{i=0}^{n-1} \ \binom{n-1}{i} i^k$$

现在的问题主要在后半部分, 由第二类 Stirling 数的性质, 得

$$\sum_{i=0}^{n-1} \ \binom{n-1}{i} \sum_{j=0}^{i} \ \begin{Bmatrix}k \\ j \end{Bmatrix}\ j!\ \binom{i}{j}$$

改变 $i, j$ 的枚举顺序, 有

$$\sum_{j=0}^{n-1}\ \begin{Bmatrix} k\\ j \end{Bmatrix} \cdot j! \ \sum_{i = j}^{n - 1}\ \binom{n-1}{i} \binom{i}{j}$$

不过要注意到 $\forall m > n, \begin{Bmatrix} n \ m \end{Bmatrix} = 0$

接下来的 trick 来源于 Tiw’s Blog, 考虑右边和式的组合意义, 即在 $n-1$ 个物品中选取 $i$ 个物品, 并在 $i$ 个物品中选择 $j$ 个的方案数. 可以发现, 这样等同于在 $n-1$ 个物品中选择 $j$ 个, 剩下部分可选可不选, 这样就同 $i$ 无关了. 可得

$$\sum_{j=0}^{n-1}\ \begin{Bmatrix} k\\ j \end{Bmatrix} \cdot j! \ \binom{n-1}{j}\ 2^{ n-1-j } \\ \sum_{j=0}^{n-1}\ \begin{Bmatrix} k\\ j \end{Bmatrix} \ \frac{(n-1)!}{(n-1-j)!}\ 2^{ n-1-j }$$

接下来就可以写了…

先计算 $k$ 对应的第二类 Stirling 数, 之后 $O(n)$ 扫一遍统计答案. 式子中间的一项在 $j$ 增加的过程中每次只多出一个乘积, 顺手维护就好了.

最后答案

$$n \cdot 2^{\frac{1}{2} (n-1)(n-2)} \sum_{j=0}^{n-1}\ \begin{Bmatrix} k\\ j \end{Bmatrix} \ \frac{(n-1)!}{(n-1-j)!}\ 2^{ n-1-j }$$

代码实现

/**************************************************************
    Problem: 5093
    User: DepletedPrism
    Language: C++
    Result: Accepted
    Time:10104 ms
    Memory:20352 kb
****************************************************************/
 
// BZOJ 5093
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MAXN = 1e6+5;
const int P = 998244353, G = 3, iG = 332748118;
 
int fpow(int base, int b, int m = P) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % m;
        base = 1LL * base * base % m, b >>= 1;
    }
    return ret;
}
 
namespace Poly {
    int r[MAXN];
    inline void init(const int& Lim, const int& L) {
        for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
    }
 
    void NTT(int* f, int Lim, int type) {
        for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
        for (int Mid = 1; Mid < Lim; Mid <<= 1) {
            int unit = fpow(type > 0? G: iG, (P-1) / (Mid << 1));
            for (int i = 0; i < Lim; i += Mid << 1) {
                int w = 1;
                for (int j = 0; j < Mid; ++j, w = 1LL * w * unit % P) {
                    int f0 = f[i+j], f1 = 1LL * w * f[i+j+Mid] % P;
                    f[i+j] = (f0 + f1) % P, f[i+j+Mid] = (f0 - f1 + P) % P;
                }
            }
        }
        if (type < 0) {
            int inv = fpow(Lim, P-2);
            for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * inv % P;
        }
    }
}
 
int n, K;
int f[MAXN], g[MAXN];
int inv[MAXN], fac[MAXN];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d", &n, &K);
    // init
    inv[0] = fac[0] = 1;
    for (int i = 1; i <= K; ++i) fac[i] = 1LL * fac[i-1] * i % P;
    inv[K] = fpow(fac[K], P-2);
    for (int i = K; i; --i) inv[i-1] = 1LL * i * inv[i] % P;
    // solve
    for (int i = 0; i <= K; ++i) {
        f[i] = (i & 1)? P-inv[i]: inv[i];
        g[i] = 1LL * fpow(i, K) * inv[i] % P;
    }
    int Lim = 1, L = 0;
    while (Lim <= 2*K) Lim <<= 1, ++L;
    Poly::init(Lim, L), Poly::NTT(f, Lim, 1), Poly::NTT(g, Lim, 1);
    for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * g[i] % P;
    Poly::NTT(f, Lim, -1);
    // output
    int ans = 0, b = 1LL * (n-1) * (n-2) / 2 % (P-1);
    int inv2 = fpow(2, P-2), mul = 1, pow2 = fpow(2, n-1);
    for (int i = 0; i < n && i <= K; ++i) {
        ans = (ans + 1LL * f[i] * mul % P * pow2 % P) % P;
        mul = 1LL * mul * (n-i-1) % P, pow2 = 1LL * pow2 * inv2 % P;
    }
    printf("%lld\n", 1LL * ans * fpow(2, b) % P * n % P);
    return 0;
}

---