「UOJ Goodbye Jihai」新年的追逐战

2020 年 04 月 23 日

定义两个简单无向图 $G_{1} =( V_{1} , E_{1}) , G_{2} =( V_{2} , E_{2})$ 的乘积为一个新的图 $G_{1} \times G_{2} =\left( V^{\star} , E^{\star} \right)$ ，其中
$\begin{aligned} V^{\star} &= \left\{ {(a, b)| a \in V_{1}, b \in V_{2} }\right\},\\ E^{\star} &=\left\{\left(( u_{1} , v_{1}) , ( u_{2} , v_{2})\right) \mid ( u_{1} , u_{2}) \in E_{1}, ( v_{1} , v_{2}) \in E_{2}\right\}. \end{aligned}$
对于正整数 $n$ ，以及给定的图 $G_{1} , G_{2} , \dotsc , G_{n}$ ，我们令
$\displaystyle{H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n}.$
若每个 $G_k$ 中每任意两点都有 $\frac12$ 的概率有边，求 $H$ 的连通块个数的期望。

$1\le n, m_k\le 10^5$ 。答案对 $998244353$ 取模。

题解

大概是一个二合一状物，我们搞出生成函数以后逐个合并。

考虑 $k=1$ 怎么做，假设 $G$ 为无标号无向图生成函数：

G = \sum_{i\ge 0} \frac {2^{\binom i 2} x^i} {i!}

则 $\ln G$ 为无标号联通无向图生成函数， $n! [x^n] G \ln G$ 即为答案。

考虑 $k=2$ 怎么做，我们需要特判下孤立点的情况。合并的结果和两边的图是否为二分图（即题解所谓没有奇环）是有关的，当且仅当两侧都是二分图时会使得生成的图对应两个联通块。

考虑无标号二分图生成函数 $B$ （可以卷积解决）：

B = \sum_{i \ge 0} \sum_{j \ge 0} \frac {2^{ij} x^{i+j}} {i! j!} = \sum_{i \ge 0} \sum_{j \ge 0} \frac {2^{\binom {i+j} 2 - \binom i 2 - \binom j 2} x^{i+j}} {i! j!}

故非平凡二分图联通块生成函数为 $G (\frac {\ln B} 2 - 1)$ ，非平凡非二分图联通块生成函数为 $G (\ln G - \frac {\ln B} 2)$ ，非平凡联通块生成函数为 $G (\ln G - 1)$ 。孤立点联通块生成函数为 $x G$ （这几个均为无标号

考虑记录下期望点数，期望非平凡二分图联通块，期望非平凡非二分图联通块，期望孤立点个数，即可合并两个图的信息，做下去即可（

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
int n, l, lim, m[N], rev[N << 2];
struct z {
  int x;
  z(int x = 0) : x(x) {}
  inline int half() { return x & 1 ? (x + mod) >> 1 : x >> 1; }
  friend inline z operator*(z a, z b) { return (long long)a.x * b.x % mod; }
  friend inline z operator-(z a, z b) { return (a.x -= b.x) < 0 ? a.x + mod : a.x; }
  friend inline z operator+(z a, z b) { return (a.x += b.x) >= mod ? a.x - mod : a.x; }
} a[N], b[N], c[N], d[N], fac[N], inv[N], ifac[N], t1[N], w[N << 2];
using poly = vector<z>;
inline z fpow(z a, int b) {
  z s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
int polyInit(int l) {
  int lim = 1, k = 0;
  while (lim < l) lim <<= 1, ++k;
  for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  static int len = 1;
  for (; len < lim; len <<= 1) {
    z wn = fpow(3, (mod - 1) / (len << 1));
    w[len] = 1;
    for (int i = 1; i < len; i++) w[i + len] = w[i + len - 1] * wn;
  }
  return lim;
}
void dft(poly &a, int lim) {
  a.resize(lim);
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int len = 1; len < lim; len <<= 1)
    for (int i = 0; i < lim; i += (len << 1))
      for (int j = 0; j < len; j++) {
        z x = a[i + j], y = a[i + j + len] * w[j + len];
        a[i + j] = x + y, a[i + j + len] = x - y;
      }
}
void idft(poly &a, int lim) {
  dft(a, lim), reverse(&a[1], &a[lim]);
  z inv = fpow(lim, mod - 2);
  for (int i = 0; i < lim; i++) a[i] = a[i] * inv;
}
poly polyInc(poly a, const poly &b) {
  a.resize(max(a.size(), b.size()));
  for (int i = 0; i < b.size(); i++) a[i] = a[i] + b[i];
  return a;
}
poly polyDec(poly a, const poly &b) {
  a.resize(max(a.size(), b.size()));
  for (int i = 0; i < b.size(); i++) a[i] = a[i] - b[i];
  return a;
}
poly polyMul(poly a, poly b) {
  int lim = polyInit(a.size() + b.size() - 1);
  dft(a, lim), dft(b, lim);
  for (int i = 0; i < lim; i++) a[i] = a[i] * b[i];
  idft(a, lim), a.resize(l);
  return a;
}
poly polyInv(poly f, int len = -1) {
  if ((len = ~len ? len : f.size()) == 1) return {fpow(f[0], mod - 2)};
  poly a(&f[0], &f[len]), b = polyInv(f, (len + 1) >> 1);
  int lim = polyInit((len << 1) - 1);
  dft(a, lim), dft(b, lim);
  for (int i = 0; i < lim; i++) a[i] = b[i] * (2 - a[i] * b[i]);
  idft(a, lim), a.resize(len);
  return a;
}
poly polyDer(poly f) {
  for (int i = 0; i <= f.size() - 2; i++) f[i] = f[i + 1] * (i + 1);
  *--f.end() = 0;
  return f;
}
poly polyInt(poly f) {
  for (int i = f.size() - 1; i >= 1; i--) f[i] = f[i - 1] * inv[i];
  *f.begin() = 0;
  return f;
}
poly polyLn(poly f) { return polyInt(polyMul(polyInv(f), polyDer(f))); }
poly A, B, C, D, E, F, G, H;
struct info {
  z n, a, b, c;
  inline z dump() { return a + b + c; }
  inline void load(int x) { n = G[x] * fac[x] * x, a = C[x] * fac[x], b = D[x] * fac[x], c = G[x - 1] * fac[x]; }
  friend inline info operator^(const info &a, const info &b) {
    static info s;
    s.n = a.n * b.n;
    s.a = 2 * a.a * b.a + a.a * b.b + a.b * b.a;
    s.b = a.b * b.b;
    s.c = a.c * b.c + a.c * (b.n - b.c) + b.c * (a.n - a.c);
    return s;
  }
} ans, tmp;
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> m[i], l = max(l, m[i] + 1);
  fac[0] = ifac[0] = inv[0] = inv[1] = 1;
  for (int i = 1; i <= l; i++) fac[i] = fac[i - 1] * i;
  for (int i = 2; i <= l; i++) inv[i] = (mod - mod / i) * inv[mod % i];
  for (int i = 1; i <= l; i++) ifac[i] = ifac[i - 1] * inv[i];
  G.resize(l), B.resize(l);
  for (int i = 0; i < l; i++) t1[i] = fpow(2, (long long)i * (i - 1) / 2 % (mod - 1));
  for (int i = 0; i < l; i++) G[i] = t1[i] * ifac[i];
  for (int i = 0; i < l; i++) B[i] = ifac[i] * fpow(t1[i], mod - 2);
  B = polyMul(B, B), B.resize(l);
  for (int i = 0; i < l; i++) B[i] = B[i] * t1[i];
  F = polyLn(G), H = G, F[1] = 0, A = polyLn(B), A[1] = 0;
  for (int i = 0; i < l; i++) A[i] = A[i].half();
  C = polyMul(G, A), C.resize(l), E = polyMul(G, F), E.resize(l), D = polyDec(E, C);
  ans.load(m[1]);
  for (int i = 2; i <= n; i++) ans = ans ^ (tmp.load(m[i]), tmp);
  cout << ans.dump().x << endl;
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论