2021牛客多校10

题号	标题	团队的状态
A	Browser Games	通过
B	Child’s play	未通过
C	Dance Party	未通过
D	Diameter Counting	未通过
E	More Fantastic Chess Problem	通过
F	Train Wreck	通过
G	Game of Death	通过
H	War of Inazuma (Easy Version)	通过
I	War of Inazuma (Hard Version)	未通过
J	Illuminations	通过
K	Walking	通过

// Author:  HolyK
// Created: Tue Aug 31 10:32:26 2021
#include <algorithm>
#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(LL v) : x((v %= P) < 0 ? v + P : v) {}
  explicit operator bool() { return !!x; }
  Z inv() const { return Z(fpow(x)); }
  Z pow(int k) const { return Z(fpow(x, k)); }
  Z operator-() const { return Z(P - x); }
  Z &operator+=(const Z &r) { return inc(x, r.x), *this; }
  Z &operator-=(const Z &r) { return dec(x, r.x), *this; }
  Z &operator*=(const Z &r) { return x = LL(x) * r.x % P, *this; }
  Z &operator/=(const Z &r) { return x = LL(x) * fpow(r.x) % P, *this; }
  inline friend Z operator+(const Z &a, const Z &b) { return Z(a) += b; }
  inline friend Z operator-(const Z &a, const Z &b) { return Z(a) -= b; }
  inline friend Z operator*(const Z &a, const Z &b) { return Z(a) *= b; }
  inline friend Z operator/(const Z &a, const Z &b) { return Z(a) /= b; }
  inline friend std::ostream &operator<<(std::ostream &os, const Z &r) {
    return os << r.x;
  }
};
constexpr int N(3e5 + 5);
Z sum[N << 2], tag[N << 2];
#define ls o << 1
#define rs o << 1 | 1
void mul(int o, Z x) {
  sum[o] *= x;
  tag[o] *= x;
}
void pushdown(int o) {
  if (tag[o].x != 1) {
    mul(ls, tag[o]), mul(rs, tag[o]), tag[o] = 1;
  }
}
void update(int o, int l, int r, int x, int y, Z z) {
  if (x <= l && r <= y) return mul(o, z);
  pushdown(o);
  int m = l + r >> 1;
  if (x < m) update(ls, l, m, x, y, z);
  if (y > m) update(rs, m, r, x, y, z);
  sum[o] = sum[ls] + sum[rs];
}
void build(int o, int l, int r) {
  tag[o] = 1;
  sum[o] = r - l;
  if (r - l == 1) return;
  int m = l + r >> 1;
  build(ls, l, m), build(rs, m, r);
}

Z c[N][2];
int m;
void add(int p, int x) {
  Z v[2] = {(1LL - p) * x, x};
  for (; p < m; p += p & -p) c[p][0] += v[0], c[p][1] += v[1];
}
void add(int l, int r, int x) {
  add(l, x), add(r + 1, -x);
}
Z ask(int n) {
  Z r[2];
  for (int p = n; p; p -= p & -p) r[0] += c[p][0], r[1] += c[p][1];
  return r[0] + r[1] * n;
}
Z ask(int l, int r) {
  return ask(r) - ask(l - 1);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, q;
  std::string s;
  std::cin >> n >> q >> s;
  std::vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) std::cin >> a[i], smax(m, a[i]);
  for (int i = 0; i < n; i++) std::cin >> b[i];
  if (s == "King") {
    std::vector<Z> c(n);
    Z ans = 1;
    for (int i = 0; i < n; i++) {
      c[i] = 1 + (a[i] - b[i] > 0) + (b[i] > 1);
      ans *= c[i];
    }
    std::cout << ans - 1 << "\n";
    while (q-- ) {
      int d;
      std::cin >> d;
      while (d--) {
        int i, x;
        std::cin >> i >> x;
        i--;
        ans /= c[i];
        b[i] += x;
        c[i] = 1 + (a[i] - b[i] > 0) + (b[i] > 1);
        ans *= c[i];
      }
      std::cout << ans - 1 << "\n";
    }
  } else if (s == "Queen") {
    Z ans;
    build(1, 1, m);
    Z i3 = Z(3).inv(), i2 = Z(2).inv();
    for (int i = 0; i < n; i++) {
      int u = b[i], v = a[i] - b[i] + 1;
      if (u > v) std::swap(u, v);
      if (1 < u) update(1, 1, m, 1, u, 3);
      if (u < v) update(1, 1, m, u, v, 2);
    }
    std::cout << sum[1] - m + 1 << "\n";
    while (q--) {
      int d;
      std::cin >> d;
      while (d--) {
        int i, x;
        std::cin >> i >> x;
        i--;
        int u = b[i], v = a[i] - b[i] + 1;
        if (u > v) std::swap(u, v);
        if (1 < u) update(1, 1, m, 1, u, i3);
        if (u < v) update(1, 1, m, u, v, i2);
        u = b[i] += x, v = a[i] - b[i] + 1;
        if (u > v) std::swap(u, v);
        if (1 < u) update(1, 1, m, 1, u, 3);
        if (u < v) update(1, 1, m, u, v, 2);
      }
      std::cout << sum[1] - m + 1 << "\n";
    }
  } else if (s == "Rook") {
    q++;
    Z ans;
    for (int i = 0; i < n; i++) ans += a[i] - 1;
    while (q--) {
      std::cout << ans << "\n";
    }
  } else if (s == "Bishop") {
    Z ans;
    for (int i = 0; i < n; i++) {
      int u = b[i], v = a[i] - b[i] + 1;
      if (u > v) std::swap(u, v);
      if (1 < u) ans += ask(1, u - 1) * 2, add(1, u - 1, 2);
      if (u < v) ans += ask(u, v - 1), add(u, v - 1, 1);
    }
    std::cout << ans << "\n";
    while (q--) {
      int d;
      std::cin >> d;
      while (d--) {
        int i, x;
        std::cin >> i >> x;
        i--;
        int u = b[i], v = a[i] - b[i] + 1;
        if (u > v) std::swap(u, v);
        if (1 < u) add(1, u - 1, -2), ans -= ask(1, u - 1) * 2;
        if (u < v) add(u, v - 1, -1), ans -= ask(u, v - 1);
        u = b[i] += x, v = a[i] - b[i] + 1;
        if (u > v) std::swap(u, v);
        if (1 < u) ans += ask(1, u - 1) * 2, add(1, u - 1, 2);
        if (u < v) ans += ask(u, v - 1), add(u, v - 1, 1);
      }
      std::cout << ans << "\n";
    }
  } else if (s == "Knight") {
    Z c, d, ans;
    for (int i = 0; i < n; i++) {
      int x = (b[i] > 1) + (a[i] - b[i] > 0);
      int y = (b[i] > 2) + (a[i] - b[i] > 1);
      ans += c * y + d * x;
      c += x, d += y;
    }
    std::cout << ans << "\n";
    while (q--) {
      int k;
      std::cin >> k;
      while (k--) {
        int i, u;
        std::cin >> i >> u;
        i--;
        int x = (b[i] > 1) + (a[i] - b[i] > 0);
        int y = (b[i] > 2) + (a[i] - b[i] > 1);
        c -= x, d -= y;
        ans -= c * y + d * x;
        b[i] += u;
        x = (b[i] > 1) + (a[i] - b[i] > 0);
        y = (b[i] > 2) + (a[i] - b[i] > 1);
        ans += c * y + d * x;
        c += x, d += y;
      }
      std::cout << ans << "\n";
    }
  } else {
    assert(false);
  }
  return 0;
}

Game of Death

\(n\) 个人，每个人等概率的选择其余的人开枪，有 \(p\) 的概率击中，所有人同时开枪，分别求存活人数为 \(0, 1, \dots, n\) 的概率。

\(2 \leq n \leq 3 \times 10^5\)

设 \(f_i\) 表示恰好有 \(i\) 个人存活的概率，\(g_i\) 表示钦定 \(i\) 个人存活的概率。容易计算 \[ g_i = \binom{n}{i}\left(1-p + \frac{p(n-i)}{n-1}\right)^i\left(1-p+\frac{p(n-i-1)}{n-1}\right)^{n-i} \] 又 \[ g_k = \sum_{i \geq k}f_i\binom{i}{k} \] 二项式反演得 \[ \begin{aligned} f_k &= \sum_{i \geq k}g_i\binom{i}{k}(-1)^{i - k}\\ &= \sum_{i \geq k}i!g_i\frac{1}{(i-k)!}\frac{1}{k!} \end{aligned} \] 这是卷积的形式。

using namespace Polynomial;
constexpr int N(1e6 + 5);
int fac[N], ifac[N];
int bin(int n, int m) {
  if (m < 0 || m > n) return 0;
  return 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P;
}
void init(int n) {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % P;
  ifac[n] = fpow(fac[n]);
  for (int i = n - 1; i > 0; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, a, b;
  std::cin >> n >> a >> b;
  init(n);
  int p = 1LL * a * fpow(b) % P;
  Poly f(n + 1), g(n + 1);
  int invn = fpow(n - 1);
  for (int i = 0; i <= n; i++) {
    f[i] = i & 1 ? P - ifac[i] : ifac[i];
    g[i] = 1LL * fpow((P + 1 - p + 1LL * p * (i - 1) % P * invn) % P, i) * fpow((P + 1 - p + 1LL * p * i % P * invn) % P, n - i) % P * ifac[i] % P;
  }
  f = f * g;
  for (int i = 0; i <= n; i++) {
    f[i] = 1LL * f[i] * fac[n] % P * ifac[n - i] % P;
  }
  for (int i = 0; i <= n; i++) {
    std::cout << f[n - i] << "\n";
  }
  return 0;
}

War of Inazuma (Easy Version)

War of Inazuma (Hard Version)

Illuminations

Walking

在一个 \(n \times m\) 的网格图上，你在 \((a, b)\)，每次移动可以向上下左右移动一格，不能移动出边界，求走 \(t\) 步的方案数。

\(1 \leq n, m, t \leq 5\times10^5\)

把两维拆开分别计算走 \(0 \dots t\) 步的方案数。

正难则反，考虑计算不合法方案数，记 \(f_i\) 表示走 \(i\) 步的不合法方案数。

发现不合法方案一定是先走到一个边界（\(0\) 或 \(n + 1\)），接下来随便走。

所以设 \(f'_i\) 表示前 \(i - 1\) 步都合法，恰好在第 \(i\) 步走到边界的方案数。

有 \[ f_n = \sum_{k = 0}^nf'_k2^{n-k} \] 写成生成函数的形式，是 \[ F = \frac{F'}{1 - 2x} \] 下面考虑如何计算 \(F'\)。

设 \(f''_i\) 表示走 \(i\) 步，最终停在边界（\(0\) 或 \(1\)）的方案数，这个可以轻易地用组合数计算。

\(f''_i\) 的方案一定是包含 \(f'_i\) 的方案的，可以发现， \(f''_k\) 表示的方案可以拆解成两个部分：先合法地走到边界，然后花费剩下的步数原地打转，或者从一个边界走到另一个边界。

设 \(g_i\) 表示走 \(i\) 步原地打转或者从一个边界移动到另一个边界的方案数，这个也可以用组合数计算。

写成生成函数的形式，是 \[ F'' = F'G \] 所以 \[ \begin{aligned} F &= \frac{F'}{1 - 2x}\\ &= \frac{F''}{G(1-2x)} \end{aligned} \] 多项式求逆即可。

using namespace Polynomial;
constexpr int N(1e6 + 5);
int fac[N], ifac[N];
int bin(int n, int m) {
  if (m < 0 || m > n) return 0;
  return 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P;
}
void init(int n) {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % P;
  ifac[n] = fpow(fac[n]);
  for (int i = n - 1; i > 0; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
}
int cal(int n, int m) {
  if (n - m & 1) return 0;
  return bin(n, (n + m) / 2);
}
Poly cal(int a, int n, int t) {
  Poly f(t + 1), g(t + 1);
  for (int i = 0; i <= t; i++) {
    g[i] = cal(i, 0);
    inc(g[i], cal(i, n + 1));
  }
  for (int i = t; i > 0; i--) {
    g[i] = (g[i] + (P - 2LL) * g[i - 1]) % P;
  }
  
  for (int i = 0; i <= t; i++) {
    f[i] = cal(i, a);
    inc(f[i], cal(i, n + 1 - a));
  }
  g = inverse(g);
  f = f * g;
  f.resize(t + 1);
  for (int i = 0, p = 1; i <= t; i++, p = 2LL * p % P) {
    f[i] = (p - f[i] + P) % P;
  }
  return f;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  init(1e6);
  int t, n, m, a, b;
  std::cin >> t >> n >> m >> a >> b;
  auto f = cal(a, n, t), g = cal(b, m, t);
  int ans = 0;
  for (int i = 0; i <= t; i++) {
    ans = (ans + 1LL * bin(t, i) * f[i] % P * g[t - i]) % P;
  }
  std::cout << ans << "\n";
  return 0;
}

最后修改于 2021-08-31