01-28模拟赛 | Egrecho47's Blog

迷宫

题目描述

定义一个 $n$ 个点，边集不确定的简单无向图，其稳定程度是每个点的点度的 $k$ 次方之和。求在所有情况下图的稳定程度之和，对 998244353 取模后输出。

题解

考虑每个点的贡献

2^{n - 1 \choose 2} \sum_{d}^{n - 1} {n - 1 \choose d} d ^ k

把 $d ^ k$ 用斯特林数换掉

2^{n - 1 \choose 2} \sum_{d}^{n - 1} {n - 1 \choose d} \sum_{i = 1}^d {d \choose i} S(k, i) i!

考虑 $\sum_{d}^{n - 1} {n - 1 \choose d} \sum_{i = 1}^d {d \choose i}$ 的一种组合意义，先选 $d$ 个，再选 $i$ 个，其实可以先钦定那 $i$ 个，然后剩下 $n - i$ 个随便选，每种方案都一一对应，所以：

2^{n - 1 \choose 2} \sum_{i = 1}^{n - 1} {n - 1 \choose i} 2^{n - 1 - i} S(k, i) i!

然后发现当 $i > k$ 时贡献为 $0$ ，所以：

2^{n - 1 \choose 2} \sum_{i = 1}^{\min (n - 1, k)} {n - 1 \choose i} 2^{n - 1 - i} S(k, i) i!

斯特林数算一下然后枚举累加就好了，由于是 $n$ 个点最后乘 $n$

/// @tags: Stiring
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const N = 1 << 19, P = 998244353, g = 3, ig = 332748118;

class Polynomial {
 private:
  int f[N];

 public:
  void NTT(bool const typ, int const n);
  int *operator&() { return f; }
  int &operator[](int index) { return f[index]; };
  int const &operator[](int index) const { return f[index]; };
} F, G;

int n, K;
int fac[N], inv[N], cvt[N];

inline ll qpow(ll base, int exp) {
  ll Res = 1;
  while (exp) {
    if (exp & 1) Res = Res * base % P;
    base = base * base % P;
    exp >>= 1;
  }
  return Res;
}

/// @param typ 正/逆向 @param n 项数 必须是2的整数次幂
inline void Polynomial::NTT(bool const typ, int const n) {
  for (int i = 1; i < n; ++i)
    if (i < cvt[i]) swap(f[i], f[cvt[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    int mid = i >> 1, wn = qpow(typ ? g : ig, (P - 1) / i);
    for (int j = 0; j < n; j += i) {
      ll wk = 1;
      for (int k = 0; k < mid; ++k, (wk *= wn) %= P) {
        ll t = wk * f[j + k + mid] % P;
        if ((f[j + k + mid] = f[j + k] - t) < 0) f[j + k + mid] += P;
        if ((f[j + k] += t) >= P) f[j + k] -= P;
      }
    }
  }
  if (!typ) {
    ll inv = qpow(n, P - 2);
    for (int i = 0; i < n; ++i) f[i] = inv * f[i] % P;
  }
}

inline int main() {
  cin >> n >> K;
  int lim = min(K, n - 1);
  int maxl = 1;
  while (maxl < lim + lim) maxl <<= 1;
  fac[0] = 1;
  for (int i = 1; i <= lim; ++i) fac[i] = (ll)fac[i - 1] * i % P;
  inv[lim] = qpow(fac[lim], P - 2);
  for (int i = lim - 1; i >= 0; --i) inv[i] = (ll)inv[i + 1] * (i + 1) % P;
  for (int i = 0; i <= lim; ++i) {
    F[i] = qpow(i, K) * inv[i] % P;
    G[i] = (i & 1) ? P - inv[i] : inv[i];
  }
  for (int i = 1; i < maxl; ++i) cvt[i] = cvt[i >> 1] >> 1 | ((i & 1) ? maxl >> 1 : 0);
  F.NTT(true, maxl), G.NTT(true, maxl);
  for (int i = 0; i < maxl; ++i) F[i] = (ll)F[i] * G[i] % P;
  F.NTT(false, maxl);
  ll ans = 0, tmp = 1;
  for (int i = 0; i <= lim; i++) {
    if ((ans += F[i] * tmp % P * qpow(2, n - i - 1) % P) >= P) ans -= P;
    tmp = tmp * (n - 1 - i) % P;
  }
  ans = ans * n % P * qpow(2, (ll)(n - 2) * (n - 1) >> 1) % P;
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("迷宫.in", "r", stdin);
  freopen("迷宫.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}