2021牛客多校9

题号	标题	团队的状态
A	A Math Challenge	通过
B	Best Subgraph	未通过
C	Cells	通过
D	Divide-and-conquer on Tree	未通过
E	Eyjafjalla	通过
F	Financial Order Execution	未通过
G	Glass Balls	通过
H	Happy Number	通过
I	Incentive Model	通过
J	Jam	通过

A Math Challenge

LOJ138 + 自然数幂和。

// Author:  HolyK
// Created: Sun Aug 15 21:59:21 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) {
  return x % P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z(int v = 0) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z inv() const {
    assert(x);
    return Z(fpow(x));
  }
  Z pow(int k) const {
    return Z(fpow(x, k));
  }
  Z &operator+=(const Z &r) {
    inc(x, r.x);
    return *this;
  }
  Z &operator-=(const Z &r) {
    dec(x, r.x);
    return *this;
  }
  Z &operator*=(const Z &r) {
    x = 1LL * x * r.x % P;
    return *this;
  }
  Z &operator/=(const Z &r) {
    x = 1LL * x * fpow(r.x) % P;
    return *this;
  }
  Z operator+(const Z &r) const {
    return Z(*this) += r;
  }
  Z operator-(const Z &r) const {
    return Z(*this) -= r;
  }
  Z operator*(const Z &r) const {
    return Z(*this) *= r;
  }
  Z operator/(const Z &r) const {
    return Z(*this) /= r;
  }
  Z operator-() const {
    return Z(P - x);
  }
  operator int() const {
    return x;
  }
};
Z bin[52][52], inv[52];
struct Info {
  Z i, x, f[52][52];
  Info() : i(0), x(0) {
    memset(f, 0, sizeof f);
  }
};
int n, m;
Info operator*(Info a, Info b) {
  Info c;
  c.i = a.i + b.i;
  c.x = a.x + b.x;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      c.f[i][j] = a.f[i][j];
    }
  }
  Z u = 1, v, bu;
  for (int j = 0; j <= n; j++, u *= a.i) {
    for (int p = j; p <= n; p++) {
      bu = bin[p][j] * u, v = 1;
      for (int k = 0; k <= m; k++, v *= a.x) {
        for (int q = k; q <= m; q++) {
          c.f[p][q] += bu * bin[q][k] * v * b.f[p - j][q - k];
        }
      }
    }
  }
  return c;
}
Info fpow(Info x, LL k) {
  Info r;
  for (; k; k >>= 1, x = x * x) {
    if (k & 1) r = r * x;
  }
  return r;
}
LL div(LL p, LL i, LL r, LL q) {
  return (p * i + r) / q; 
}
Info cal(LL p, LL r, LL q, LL n, const Info &x, const Info &y) {
  if (n < 0) return Info();
  if (r >= q) {
    return fpow(y, r / q) * cal(p, r % q, q, n, x, y);
  }
  if (p >= q) {
    return x * cal(p % q, p % q + r, q, n - 1, fpow(y, p / q) * x, y);
  }
  if (p == 0) {
    return fpow(x, n + 1);
  }
  LL m = div(p, n, r, q);
  return cal(q, q - r + p - 1, p, m - 1, y, x) * fpow(x, n + 1 - (!m ? 0 : div(q, m, p - r - 1, p)));
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (int i = 0; i <= 51; i++) {
    bin[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      bin[i][j] = bin[i - 1][j] + bin[i - 1][j - 1];
    }
  }
  int a, b, c, p, q, n;
  std::cin >> a >> b >> c >> p >> q >> n;
  q++;
  ::n = p, ::m = q;
  Info x, y;
  x.i = x.f[0][0] = y.x = 1;
  auto pw = cal(a, b, c, n, x, y);
  {
    std::vector<std::vector<Z>> a(q, std::vector<Z>(q + 1));
    Z sum = 0;
    for (int i = 0; i < q; i++) {
      for (int j = 0; j < q; j++) {
        a[i][j] = fpow(i + 1, j + 1);
      }
      a[i].back() = sum += fpow(i + 1, q - 1);
    }
    for (int i = 0, j; i < q; i++) {
      for (j = i; j < q; j++) {
        if (!a[j][i]) continue;
        std::swap(a[i], a[j]);
        break;
      }
      assert(a[i][i]);
      Z inv = a[i][i].inv();
      for (int k = 0; k <= q; k++) a[i][k] *= inv;
      for (j = 0; j < q; j++) {
        if (j == i || !a[j][i]) continue;
        for (int k = q; k >= i; k--) {
          a[j][k] -= a[j][i] * a[i][k];
        }
      }
    }
    Z ans;
    for (int i = 0; i < q; i++) {
      ans += pw.f[p][i + 1] * a[i].back();
    }
    std::cout << ans << "\n";
  }
  return 0;
}

Glass Balls

Solution 1

很难直接计算 \(f(i)\) 。

考虑条件期望，设事件 \(C_i\) 表示点 \(i\) 合法，即最多有一个儿子可以放行，事件 \(N_i\) 表示 \(i\) 到根这条路上的点合法，事件 \(N\) 表示整棵树合法。

设 \(X_{i, s}\) 表示球 \(i\) 从 \(s\) 开始，不考虑碰撞答案清零，会经过多少条边，特别地，记 \(X_i = X_{i, i}\)。

可以发现，\(X_{i,s}\) 只和 \(i\) 到根的路径上的情况有关，和其他事件是独立的，所以有 \[ \begin{aligned} E(X|N) &= \sum_{}E(X_i|N)\\ &= \sum\sum x\frac{P(X_i = x,N)}{P(N)}\\ &= \sum\sum x\frac{P(X_i = x,N_{f_i}, N-N_{f_i})}{P(N_{f_i}, N-N_{f_i})}\\ &= \sum\sum x\frac{P(X_i = x,N_{f_i})}{P(N_{f_i})}\\ &= \sum E(X_i|N_{f_i}) \end{aligned} \] 设 \(Y_i\) 表示 \(i\) 的儿子中可以通过的是哪个（可以都没有，此时 \(Y=0\) ）。

根据期望的线性性，有 \[ \begin{aligned} E(X_i | N_{f_i}) &= E((X_{i, f_i} + 1) | N_{f_i})\\ &= E(X_{i, f_i}|N_{f_i}) + P(Y_{f_i} = i | N_{f_i})\\ &= [E(X_{f_i}|N_{f_{f_i}}) + 1]P(Y_{f_i} = i | C_{f_i})\\ \end{aligned} \] 答案是 \(E(X, N) = E(X|N)P(N)\)。

// Author:  HolyK
// Created: Sat Aug 14 21:08:18 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) {
  return x % P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z(int v = 0) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z inv() const {
    assert(x);
    return Z(fpow(x));
  }
  Z pow(int k) const {
    return Z(fpow(x, k));
  }
  Z &operator+=(const Z &r) {
    inc(x, r.x);
    return *this;
  }
  Z &operator-=(const Z &r) {
    dec(x, r.x);
    return *this;
  }
  Z &operator*=(const Z &r) {
    x = 1LL * x * r.x % P;
    return *this;
  }
  Z &operator/=(const Z &r) {
    x = 1LL * x * fpow(r.x) % P;
    return *this;
  }
  Z operator+(const Z &r) const {
    return Z(*this) += r;
  }
  Z operator-(const Z &r) const {
    return Z(*this) -= r;
  }
  Z operator*(const Z &r) const {
    return Z(*this) *= r;
  }
  Z operator/(const Z &r) const {
    return Z(*this) /= r;
  }
  Z operator-() const {
    return Z(P - x);
  }
  operator int() const {
    return x;
  }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  Z p, np;
  std::cin >> n >> p.x;
  np = Z(1) - p;
  std::vector<std::vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int x;
    std::cin >> x;
    x--;
    g[x].push_back(i);
  }
  Z ans, prod = 1;
  std::function<void(int, Z)> dfs = [&](int x, Z d) {
    ans += d;
    if (!g[x].size()) {
      return;
    }
    Z k = p.pow(g[x].size() - 1) * np;
    Z v = k * Z(g[x].size()) + p.pow(g[x].size());
    prod *= v;
    k /= v;
    for (int y : g[x]) {
      dfs(y, (d + Z(1)) * k);
    }
  };
  dfs(0, 0);
  std::cout << ans * prod << "\n";
  return 0;
}

Solution 2

将起点和终点交换，考虑计算每个点向下能走多少距离。

设 \(f(i)\) 表示在 \(i\) 的子树合法的情况下，\(i\) 向下走的距离，\(s(i)\) 表示在 \(i\) 的子树合法的情况下，\(i\) 子树的答案和，\(v(i)\) 表示 \(i\) 的子树合法的概率。

详细推导略。

// Author:  HolyK
// Created: Sun Aug 15 10:11:38 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) {
  return x % P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z(int v = 0) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z inv() const {
    assert(x);
    return Z(fpow(x));
  }
  Z pow(int k) const {
    return Z(fpow(x, k));
  }
  Z &operator+=(const Z &r) {
    inc(x, r.x);
    return *this;
  }
  Z &operator-=(const Z &r) {
    dec(x, r.x);
    return *this;
  }
  Z &operator*=(const Z &r) {
    x = 1LL * x * r.x % P;
    return *this;
  }
  Z &operator/=(const Z &r) {
    x = 1LL * x * fpow(r.x) % P;
    return *this;
  }
  Z operator+(const Z &r) const {
    return Z(*this) += r;
  }
  Z operator-(const Z &r) const {
    return Z(*this) -= r;
  }
  Z operator*(const Z &r) const {
    return Z(*this) *= r;
  }
  Z operator/(const Z &r) const {
    return Z(*this) /= r;
  }
  Z operator-() const {
    return Z(P - x);
  }
  operator int() const {
    return x;
  }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  Z p;
  std::cin >> p.x;
  Z np = Z(1) - p;
  std::vector<std::vector<int>> g(n);
  for (int i = 1, x; i < n; i++) {
    std::cin >> x;
    g[x - 1].push_back(i);
  }
  std::vector<Z> f(n), s(n), v(n);
  std::function<void(int)> dfs = [&](int x) {
    v[x] = 1;
    if (!g[x].size()) {
      return;
    }
    for (int y : g[x]) {
      dfs(y);
      v[x] *= v[y];
    }
    Z k = p.pow(g[x].size() - 1) * np;
    Z c = k * Z(g[x].size()) + p.pow(g[x].size());
    for (int y : g[x]) {
      Z py = v[x] / v[y];
      s[x] += s[y] * py * c;
      f[x] += (f[y] + v[y]) * py * k;
    }
    v[x] *= c;
    s[x] += f[x];
  };
  dfs(0);
  std::cout << s[0] << "\n";
  return 0;
}