BZOJ 5093: [Lydsy1711月赛]图的价值

Description
“简单无向图”是指无重边、无自环的无向图（不一定连通）。
一个带标号的图的价值定义为每个点度数的k次方的和。
给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。
因为答案很大，请对998244353取模输出。

Input
第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。

Output
 输出一行一个整数，即答案对998244353取模的结果。

Sample Input
6 5
Sample Output
67584000
HINT
Source
本OJ付费获取

\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
我是分割线--------------
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\

枚举图统计答案显然是不好做的。
我们枚举每一个点向其他点连边，那么贡献就是：
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{n-1}_{i=0}\binom {n-1} i \cdot i^k$$

下面是：
性感rockdu，在线推导
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{n-1}_{i=0}\binom {n-1} i \cdot \sum^{k}_{j=0} \left\{ \begin{matrix}k\\j\end{matrix} \right\}i^{\underline j}$$
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{k}_{j=0}\left\{ \begin{matrix}k\\j\end{matrix} \right\} j!\sum^{n-1}_{i=0}\binom {n-1} i \binom i j$$
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{k}_{j=0}\left\{ \begin{matrix}k\\j\end{matrix} \right\} j!\sum^{n-1}_{i=0}\binom {n-1} j \binom {n-j-1} {i-j}$$
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{k}_{j=0}\left\{ \begin{matrix}k\\j\end{matrix} \right\} \binom {n-1} jj!\sum^{n-1}_{i=0} \binom {n-j-1} {n-i-1}$$
$$n\cdot 2^{\binom {n-1} 2}\cdot \sum^{k}_{j=0}\left\{ \begin{matrix}k\\j\end{matrix} \right\} \binom {n-1} jj!\cdot2^{n-j-1}$$
wow！然后我们就可以算了耶。
最后一个计算的复杂度就是$O(k)$的。
然而我们不会求斯特林数啊……QAQ
考虑容斥，我们枚举至少有一个为空，至少有两个为空……：
$$\left\{ \begin{matrix}k\\j\end{matrix} \right\}=\sum^{j}_{i=0}(-1)^i\cdot \binom j i \frac{(j-i)^k}{j!}\\=\sum^{j}_{i=0}\frac{(-1)^i}{j!}\cdot \binom j {j-i} (j-i)^k$$
变成卷积形式，NTT一下就van事dark吉
```
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<complex>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 4e5 + 5;
const int P = 998244353, G = 3;
int N, mx2p, R[maxn << 1], inv;
int A[maxn << 1], B[maxn << 1], step[maxn << 1], istep[maxn << 1];
void init(int n) {
    for(N = 1; N <= n; N <<= 1) ++mx2p;
    for(register int i = 0; i < N; ++i)
        R[i] = (R[i >> 1] >> 1) | ((i & 1) << mx2p - 1);
}
 
LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % P;
        b >>= 1, a = a * a % P;
    }
    return ans;
}
 
void NTT(int * a, int type) {
    for(register int i = 0; i < N; ++i) if(i < R[i]) swap(a[i], a[R[i]]);
    for(register int i = 1; i < N; i <<= 1) {
        int Wn = fpow(G, (P - 1) / (i << 1));
        if(type == -1) Wn = fpow(Wn, P - 2);
        for(register int j = 0, p = i << 1; j < N; j += p) {
            int w = 1;
            for(register int k = 0; k < i; ++k, w = 1LL * w * Wn % P) {
                int x = a[j + k], y = 1LL * a[j + k + i] * w % P;
                a[j + k] = ((x + y) % P + P) % P;
                a[j + k + i] = ((x - y) % P + P) % P;
            }
        }
    }
}
int n, k;
void pre(int k) {
    step[0] = 1;
    for(register int i = 1; i <= k; ++i)
        step[i] = 1ll * step[i - 1] * i % P;
    istep[k] = fpow(step[k], P - 2);
    for(register int i = k - 1; i >= 0; --i)
        istep[i] = 1ll * istep[i + 1] * (i + 1) % P;
}
int C(int a, int b) {
    return ((1ll * step[a] * istep[a - b]) % P) * istep[b] % P;
}
int ans = 0, DPow = 1, tp;
int main() {
    scanf("%d%d", &n, &k);
    pre(k << 1);
    for(register int i = 0; i <= k; ++i) {
        A[i] = (((i & 1) ? -1 : 1) * istep[i] + P) % P;
        B[i] = 1ll * fpow(i, k) * istep[i] % P;
    }
    init(k << 1);
    tp = min(n - 1, k);
    inv = fpow(N, P - 2);
    NTT(A, 1), NTT(B, 1);
    for(register int i = 0; i <= N; ++i) 
        A[i] = 1ll * A[i] * B[i] % P;
    NTT(A, -1);
    for(register int i = 0; i <= N; ++i)
        A[i] = 1ll * A[i] * inv % P;
    for(register int i = 0; i <= tp; ++i) {
        A[i] = ((1ll * A[i] * DPow) % P) * fpow(2, n - 1 - i) % P;
        ans = (ans + A[i]) % P, DPow = 1ll * DPow * (n - 1 - i) % P;
    }
    ans = 1ll * ans * n % P;
    //求2^(ll)要用费马小定理 
    ans = 1ll * ans * fpow(2, (1ll * (n - 2) * (n - 1) / 2) % (P - 1)) % P;
    printf("%d", ans);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链