【BZOJ5093】圖的價值（第二類斯特林數，NTT）

Description

“簡單無向圖”是指無重邊、無自環的無向圖（不一定連通）。

一個帶标号的圖的價值定義為每個點度數的k次方的和。

給定n和k，請計算所有n個點的帶标号的簡單無向圖的價值之和。

因為答案很大，請對998244353取模輸出。

Solution

容易得到題目就是要求：

n×2(n−1)(n−2)2∑i=0n−1(n−1i)ik n × 2 ( n − 1 ) ( n − 2 ) 2 ∑ i = 0 n − 1 ( n − 1 i ) i k

現在主要是要轉化後面那個 ∑n−1i=0(n−1i)ik ∑ i = 0 n − 1 ( n − 1 i ) i k 。

直接套路地用第二類斯特林數推導：

∑i=0n−1(n−1i)∑j=0i(ij){kj}j! ∑ i = 0 n − 1 ( n − 1 i ) ∑ j = 0 i ( i j ) { k j } j !

然後我從這個時候開始就腦殘了，，我發現 {kj}j! { k j } j ! 不是可以用第二類斯特林數的展開式嗎？？我以前怎麼一直沒發現呢。然後開始狂推柿子，結果越推越複雜，走上了一條不歸路。

後來絕望了，看題解才發現，，這智商真的要退役了。。。

剩下的推導：

将 ∑i ∑ i 和 ∑j ∑ j 交換

∑j=0n−1{kj}j!∑i=jn−1(n−1i)(ij) ∑ j = 0 n − 1 { k j } j ! ∑ i = j n − 1 ( n − 1 i ) ( i j )

∑n−1i=j(n−1i)(ij) ∑ i = j n − 1 ( n − 1 i ) ( i j ) 的意義： n−1 n − 1 個物品中選 j j 個物品，其他的亂放，是以是(n−1j)2n−1−j(n−1j)2n−1−j

是以最終的柿子就是：

n×2(n−1)(n−2)2∑j=0n−1{kj}j!2n−j−1(n−1j) n × 2 ( n − 1 ) ( n − 2 ) 2 ∑ j = 0 n − 1 { k j } j ! 2 n − j − 1 ( n − 1 j )

因為 n n 比較大，是以這樣仍然不太好算，我們發現j!×(n−1j)j!×(n−1j)其實就是 (n−1) ( n − 1 ) 的 j j 次下降幂：

n×2(n−1)(n−2)2∑j=0n−1{kj}2n−j−1(n−1)j⎯n×2(n−1)(n−2)2∑j=0n−1{kj}2n−j−1(n−1)j_

然後用NTT在 O(nlog2n) O ( n l o g 2 n ) 的時間複雜度内預處理出所有的 {kj} { k j } ，直接算就行了。

Source

/************************************************
 * Au: Hany01
 * Date: Mar 24th, 2018
 * Prob: [BZOJ5093] 圖的價值
 * Email: [email protected]
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (998244353)
#define g0 (3)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b,  : ; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b,  : ; }

inline int read()
{
    register int _, __; register char c_;
    for (_ = , __ = , c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << ) + (_ << ) + (c_ ^ );
    return _ * __;
}

inline LL Pow(LL a, LL b)
{
    LL Ans = ;
    for ( ; b; b >>= , (a *= a) %= Mod) if (b & ) (Ans *= a) %= Mod;
    return Ans;
}

const int maxn = ;

LL n, fac[maxn], ifac[maxn], S[maxn], B[maxn], powg[maxn], invg[maxn];
int k, N, rev[maxn], cnt;

inline void NTT(LL* a, bool type)
{
    rep(i, N) if (rev[i] > i) swap(a[i], a[rev[i]]);
    for (int i = ; i <= N; i <<= ) {
        LL wn = type ? powg[i] : invg[i];
        for (int j = ; j < N; j += i) {
            LL w = ;
            rep(k, i >> ) {
                LL x = a[j + k], y = a[j + (i >> ) + k] * w % Mod;
                a[j + k] = (x + y) % Mod, a[j + (i >> ) + k] = (x - y + Mod) % Mod;
                (w *= wn) %= Mod;
            }
        }
    }
    if (!type) {
        LL invn = Pow(N, Mod - );
        rep(i, N) (a[i] *= invn) %= Mod;
    }
}

int main()
{
#ifdef hany01
    File("bzoj5093");
#endif

    n = read(), k = read();

    fac[] = ;
    For(i, , k) fac[i] = fac[i - ] * i % Mod;
    ifac[k] = Pow(fac[k], Mod - );
    Fordown(i, k, ) ifac[i - ] = ifac[i] * i % Mod;

    For(i, , k)
        S[i] = (i & ) ? (Mod - ifac[i]) : ifac[i],
        B[i] = Pow(i, k) * ifac[i] % Mod;

    for (N = ; N < (k << ); N <<= , ++ cnt) ;
    int invg0 = Pow(g0, Mod - );
    for (int i = ; i <= N; i <<= )
        powg[i] = Pow(g0, (Mod - ) / i), invg[i] = Pow(invg0, (Mod - ) / i);
    rep(i, N) rev[i] = (rev[i >> ] >> ) | ((i & ) << (cnt - ));

    NTT(S, ), NTT(B, );
    rep(i, N) (S[i] *= B[i]) %= Mod;
    NTT(S, );

    LL Ans = , down = ;
    For(j, , min(k, (int)(n - )))
    {
        (Ans += S[j] * Pow(, n - j - ) % Mod * down % Mod) %= Mod;
        (down *= (n -  - j)) %= Mod;
    }
    (Ans *= n * Pow(, (n - ) * (n - ) >> ) % Mod) %= Mod;
    printf("%lld\n", Ans);

    return ;
}
//範增一去無謀主，韓信原來是逐臣。
//    -- 嚴遂成《烏江項王廟》