[题解] [BZOJ5093] 图的价值

佚名 4年前 (2020-01-17) 随笔 735人围观抢沙发百度已收录

题面

题解

由题面, 我们可以得出这样一个 ** 式子
\[ \displaystyle ans = \sum_{\forall G}\sum_{i=1}^{n}d_i^k \]
其中 \(d_i\) 代表 \(i\) 点的度数

这个式子意为, 对于任意的一个简单无向图, 把每个点的答案加上...

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

这个.... 似乎并不好算, 我们尝试对于某一个点 \(i\) , 把他在每个图中的贡献放到一起讨论看一看

首先, 度数不同肯定贡献不同, 我们要枚举贡献

那这个贡献会算多少次呢

注意到我们并不需要图联通, 只要没有自环和重边即可

那么对于其他的 \(n - 1\) 个点, 他们之间可以任意连边

所以我们就将上式转化为
\[ \displaystyle ans = \sum_{i=1}^n\sum_{d=0}^{n-1}\binom{n-1}{d}d^k*2^{\frac{(n - 1)(n - 2)}{2}} \]
代表我们对于 \(i\) 点, 选 \(d\) 条边连出去, 有 \(n - 1\) 条边可选, 然后其他的点随便连

接着我们发现每一个点最后的贡献都是相同的, 这个枚举的 \(i\) 似乎并没有什么用

所以有
\[ \displaystyle ans = n*2^{\frac{(n - 1)(n - 2)}{2}}\sum_{d=0}^{n-1}\binom{n-1}{d}d^k \]
后面这个式子似乎在哪里见过

然后按照上面的推导, 最后化出来是这个样子的
\[ \displaystyle ans = n*2^{\frac{(n - 1)(n - 2)}{2}}\sum_{i=0}^{k}i!\begin{Bmatrix}k\\i\end{Bmatrix}\binom{n-1}{i}2^{n-i} \]
但是这个题中的 \(k\) 比较大, 这个第二类斯特林数有点难搞

有了!

我们发现第二类斯特林数有这样一个递推式
\[ \displaystyle \begin{aligned}\begin{Bmatrix}n\\m\end{Bmatrix}&=\frac{1}{m!}\sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n\\&=\frac{1}{m!}\sum_{i=0}^m(-1)^i\frac{m!}{i!(m-i)!}(m-i)^n\\&=\sum_{i=0}^m\frac{(-1)^i}{i!}*\frac{(m-i)^n}{(m-i)!}\end{aligned} \]
这是个卷积, NTT 求一下就好了

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 200005;
const int mod = 998244353; 
using namespace std;
 
int n, m, k, len, lim, r[N << 2], a[N << 2], b[N << 2], g, gg, fac[N], inv[N], ans; 
 
template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}
 
int fpow(int x, int y)
{
    int res = 1;
    for( ; y; y >>= 1, x = 1ll * x * x % mod)
        if(y & 1) res = 1ll * res * x % mod;
    return res; 
}
 
void ntt(int *p, int opt)
{
    for(int i = 0; i < k; i++)
        if(i < r[i]) swap(p[i], p[r[i]]);
    for(int i = 1; i < k; i <<= 1)
    {
        int rt = fpow(opt == 1 ? g : gg, (mod - 1) / (i << 1));
        for(int j = 0; j < k; j += (i << 1))
        {
            int w = 1;
            for(int l = j; l < j + i; l++, w = 1ll * w * rt % mod)
            {
                int x = p[l], y = 1ll * w * p[l + i] % mod;
                p[l] = (x + y) % mod, p[l + i] = (x - y + mod) % mod; 
            }
        }
    }
}
 
void prepare1()
{
    g = 3, gg = fpow(g, mod - 2);
    for(int i = (fac[0] = 1); i <= k; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[k] = fpow(fac[k], mod - 2);
    for(int i = k - 1; i >= 0; i--)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod; 
}
 
void prepare2()
{
    for(int i = 0; i <= k; i++)
        a[i] = 1ll * (i & 1 ? mod - 1 : 1) * inv[i] % mod;
    for(int i = 0; i <= k; i++)
        b[i] = 1ll * fpow(i, k) * inv[i] % mod;
    for(len = 2 * k, k = 1; k <= len; k <<= 1, lim++); lim--;
    for(int i = 0; i < k; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << lim);
    ntt(a, 1), ntt(b, 1);
    for(int i = 0; i < k; i++)
        a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a, -1);
    int tmp = fpow(k, mod - 2);
    for(int i = 0; i < k; i++)
        a[i] = 1ll * a[i] * tmp % mod; 
}
 
int main()
{
    n = read <int> (), k = read <int> (), m = min(n - 1, k);
    prepare1(), prepare2(); 
    for(int res = 1, i = 0; i <= m; res = 1ll * res * (n - i - 1) % mod, i++)
        ans = (ans + 1ll * res * a[i] % mod * fpow(2, n - i - 1) % mod) % mod;
    ans = 1ll * ans * n % mod * fpow(2, 1ll * (n - 1) * (n - 2) / 2 % (mod - 1)) % mod;
    printf("%d\n", ans); 
    return 0; 
}