danihao123's Blog

求\(\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!\)。

\(1\leq n\leq 10^5\)。

统计的时候，考虑每个店对每个图的贡献，可以看出答案是：

\[n2^{\tfrac{(n - 1)(n - 2)}{2}}\,\sum_{i = 0}^{n - 1} \binom{n - 1}{i} i^k\]

求和号前面还好说，主要看求和号后面的咋搞。

后面的那一部分是个经典题吧……但我还是来推导一番吧：

\[
\begin{aligned}
\sum_{i = 0}^{m} \binom{m}{i} i^k&= \sum_{i = 0}^{m} \binom{m}{i}\sum_{j = 0}^k S(k, j) j!\binom{i}{j}\\
&= \sum_{j = 0}^k S(k, j) j! \sum_{i = 0}^m \binom{m}{i}\binom{i}{j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} \sum_{i = 0}^{m} \binom{n - j}{i - j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} 2^{m - j}
\end{aligned}
\]

然后如果我们能高效的求出某一行的第二类斯特林数，那么问题就迎刃而解了。

考虑斯特林反演（这本质上是一个容斥，用二项式反演也可以推导）：

\[S(k, j) = \sum_{i = 0}^j \frac{(-1)^{j - i}}{(j - i)!} \cdot \frac{i^k}{i!}\]

这个东西很显然是一个卷积……而且模数还很友好（UOJ模数），用NTT求出一行的第二类斯特林数即可。

代码：

/**************************************************************
    Problem: 5093
    User: danihao123
    Language: C++
    Result: Accepted
    Time:22632 ms
    Memory:25824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 998244353LL;
const ll bs = 3LL;
inline ll pow_mod(const ll &a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
inline ll inv(const ll &x) {
  return pow_mod(x, ha - 2LL);
}
 
inline int flip(const int &bi, const int &x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
inline void ntt(ll *A, const int &bi, const int &len, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi = pow_mod(bs, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi = inv(xi);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (w * y) % ha) % ha;
        A[j + L] = (x - (w * y) % ha + ha) % ha;
        w = (w * xi) % ha;
      }
    }
  }
}
 
const int maxn = 800005;
ll A[maxn], B[maxn];
ll fac[maxn], down[maxn];
int main() {
  ll n; int k; scanf("%lld%d", &n, &k);
  if(n == 1) {
    puts("0"); return 0;
  }
  int len = 1, bi = 0;
  while(len <= (2 * k)) {
    len <<= 1; bi ++;
  }
  fac[0] = 1LL;
  for(int i = 1; i <= k; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    A[i] = (inv(fac[i]) * pow_mod(ha - 1LL, i)) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    B[i] = inv(fac[i]);
    B[i] = (B[i] * pow_mod(i, k)) % ha;
  }
  ntt(A, bi, len); ntt(B, bi, len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * B[i]) % ha;
  }
  ntt(A, bi, len, true);
  ll inv_l = inv(len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * inv_l) % ha;
  }
#ifdef LOCAL
  for(int i = 0; i <= k; i ++) {
    printf("%lld ", A[i]);
  }
  puts("");
#endif
  down[0] = 1LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    down[i] = (down[i - 1] * (n - (ll(i)))) % ha;
  }
  ll ans = 0LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    ll delta = (A[i] * down[i]) % ha;
    delta = (delta * pow_mod(2, n - 1LL - (ll(i)))) % ha;
    ans = (ans + delta) % ha;
  }
  ans = (ans * pow_mod(2LL, (n - 1LL) * (n - 2LL) / 2LL)) % ha;
  ans = (ans * n) % ha;
  printf("%lld\n", ans);
  return 0;
}

第一次用到第二类斯特林数……

首先众所周知第二类斯特林数有一个很好康的式子：

\[x^k = \sum_{i = 0}^k S(k, i) x^{\underline{i}}\]

然后带进去试试？一番化简之后得到：

\[E_u = \sum_{i = 0}^k S(k, i) \sum_{v = 1}^n dist(u, v)^{\underline{i}}\]

那个下降幂很恶心……把它强行搞成组合数后发现：

\[E_u = \sum_{i = 0}^k S(k, i) i! \sum_{v = 1}^n \binom{dist(u, v)}{i}\]

然后考虑每个点预处理后面那个和式……显然可以树形DP苟。用经典的树形DP套路，设两个状态分别表示一个点的子树内部的贡献以及外面的点给他的贡献。至于转移，由于那是个组合数，所以可以考虑用Pascal定理苟……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <utility>
const int maxn = 50005;
const int maxk = 505;
const int ha = 10007;
int first[maxn];
int next[maxn << 1], to[maxn << 1];
int cnt;
void add_edge(int u, int v) {
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v;
}

int n, k;
int down[maxn][maxk];
void dfs_1(int x, int fa = 0) {
  down[x][0] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != fa) {
      dfs_1(v, x);
      down[x][0] = (down[x][0] + down[v][0]) % ha;
      for(int j = 1; j <= k; j ++) {
        down[x][j] = (down[x][j] + down[v][j] + down[v][j - 1]) % ha;
      }
    }
  }
}
int up[maxn][maxk];
void dfs_2(int x, int fa = 0) {
  if(fa) {
    up[x][0] = n - down[x][0];
    for(int j = 1; j <= k; j ++) {
      up[x][j] = (up[fa][j] + up[fa][j - 1] + down[fa][j] + down[fa][j - 1]) % ha;
      up[x][j] = (up[x][j] - (2 * down[x][j - 1]) % ha + ha) % ha;
      up[x][j] = (up[x][j] - down[x][j] + ha) % ha;
      if(j > 1) up[x][j] = (up[x][j] - down[x][j - 2] + ha) % ha;
    }
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != fa) {
      dfs_2(v, x);
    }
  }
}

int S[maxk][maxk];
int fac[maxn];
void process() {
  S[1][1] = 1;
  for(int i = 2; i <= k; i ++) {
    S[i][0] = 0;
    for(int j = 1; j < i; j ++) {
      S[i][j] = ((j * S[i - 1][j]) % ha + S[i - 1][j - 1]) % ha;
    }
    S[i][i] = 1;
  }
  fac[0] = 1;
  for(int i = 1; i <= n; i ++) {
    fac[i] = (fac[i - 1] * (i % ha)) % ha;
  }
}

int main() {
  int T; scanf("%d", &T);
  n = 50000; k = 500; process();
  while(T --) {
    scanf("%d%d", &n, &k);
    cnt = 0; memset(first, 0, sizeof(first));
    for(int i = 0; i < n - 1; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      add_edge(u, v); add_edge(v, u);
    }
    memset(down, 0, sizeof(down));
    memset(up, 0, sizeof(up));
    dfs_1(1); dfs_2(1);
    for(int i = 1; i <= n; i ++) {
      int ans = 0;
      for(int j = 1; j <= k; j ++) {
        int f_v = (down[i][j] + up[i][j]) % ha;
        ans = (ans + (S[k][j] * ((f_v * fac[j]) % ha)) % ha) % ha;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}