[ARC185D] Random Walk on Tree 题解

JiaY19 / 2024-10-23 / 原文

一个很套路的做法。

思路

题目要求走完整个树的时间，这并不好算，容易想到 min-max 容斥。

依据 min-max 容斥，我们可以轻松把它转化成第一次走到所有子集的时间。

考虑在这道题中，有什么特殊的。

第一，任何包含根节点的子集答案都是零。

第二，由于我们只关心第一次走到的点的时间，因此假如一个点的祖先被选中，那么这个点是否选中是无关紧要的。

这些无关紧要的点地位相同，所以我们可以一起考虑。

假设有 $n$ 个点是无关紧要的。

它们对答案的贡献是什么呢？

是：

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

这是非常令人熟悉的二项式定理。

因此：

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

我们发现，只有当 $n=0$ 的时候才对答案有贡献。

在 $n=0$ 的时候，每一条链只有最底部的点可能被选。

现在计算这样的时间即可。

首先，对于底部被选的链而言。

我们设 $f_i$ 表示到达深度为 $i$ 的点还要走的期望步数，根节点的深度为 $0$。

那么有：

\[\begin{align} f_m&=0\nonumber\\ f_{m-1}&=\frac{(f_m+f_{m-2})}{2}+1\nonumber\\ &=\frac{f_{m-2}}{2}+1\nonumber\\ f_{m-2}&=\frac{f_{m-3}+f_{m-1}}{2}+1\nonumber\\ &=\frac{f_{m-3}+\frac{f_{m-2}}{2}+1}{2}+1\nonumber\\ &=\frac{2f_{m-3}}{3}+2\nonumber\\ f_{m-i}&=\frac{if_{m-i-1}}{i+1}+i\nonumber\\ \end{align} \]

对于底部没有被选的链而言。

有：

\[\begin{align} f_n&=f_{m-1}+1\nonumber\\ f_{m-1}&=\frac{(f_n+f_{m-2})}{2}+1\nonumber\\ &=f_{m-2}+3\nonumber\\ f_{m-i}&=f_{m-i}+2\times i +1\nonumber\\ \end{align} \]

所有期望都可以推到根上。

因此，假设有 $i$ 条链被选，则有 $(n-i)$ 条链没有被选：

\[f_{0}=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(f_0+2\times m-1)}{n}+1 \]

可以继续化简。

\[\begin{align} f_{0}&=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(f_0+2\times m-1)}{n}+1\nonumber\\ \frac{i}{n}f_{0}&=\frac{i(\frac{(m-1)f_0}{m}+m-1)+(n-i)(2\times m-1)}{n}+1\nonumber\\ (\frac{i}{n}-\frac{i(m-1)}{nm})f_{0}&=\frac{i(m-1)+(n-i)(2\times m-1)}{n}+1\nonumber\\ (i-\frac{i(m-1)}{m})f_{0}&=i(m-1)+(n-i)(2\times m-1)+n\nonumber\\ \frac{i}{m}f_{0}&=i(m-1)+(n-i)(2\times m-1)+n\nonumber\\ \end{align} \]

算出 $f_0$ 后，不要忘记乘负一和组合数的系数。

时间复杂度：$O(n\log mod)$。

瓶颈在求逆元，可以线性预处理，但没有必要。

Code

/*
  ! 前途似海，来日方长。
  ! Created: 2024/10/13 21:48:58
*/
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();

using i64 = long long;
using pii = pair<int, int>;

bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;

int n, m;

namespace Math {
int Fc[1000010], Iv[1000010];
template<typename T> inline void add(T&x, int y) { if ((x += y) >= mod) x -= mod; }
template<typename T> inline void del(T&x, int y) { if ((x -= y) < 0) x += mod; }
template<typename T> inline void add(T&x, int y, int z) { x = (x + (long long) y * z) % mod; }
template<typename T> inline void mo(T&x) { x = (x % mod + mod) % mod; }
inline long long power(long long x, long long y) {
  long long res = 1;
  while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y /= 2; }
  return res;
}
inline void init(int n) {
  Fc[0] = 1;
  for (int i = 1; i <= n; i++) Fc[i] = (long long) Fc[i - 1] * i % mod; Iv[n] = power(Fc[n], mod - 2);
  for (int i = n; i >= 1; i--) Iv[i - 1] = (long long) Iv[i] * i % mod;
}
inline long long C(int x, int y) { return (x < 0 || y < 0 || x < y ? 0 : (long long) Fc[x] * Iv[y] % mod * Iv[x - y] % mod); }
} using namespace Math;

signed main() {
  JYFILE19();
  cin >> n >> m, init(n);
  int ns = 0;
  fro(i, 1, n) {
    int x = C(n, i);
    int up = (i * (m - 1) + (n - i) * (2 * m - 1)) % mod;
    int dw = (i * power(m, mod - 2)) % mod;
    int sm = ((up + n) * power(dw, mod - 2)) % mod;
    ns = (ns + (i & 1 ? 1 : -1) * x * sm) % mod;
  }
  cout << (ns % mod + mod) % mod << "\n";
  return 0;
}

bool ED;
inline void JYFILE19() {
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  srand(random_device{}());
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED - &ST) / 1048576.), LIM = 32;
  cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}