「UR #17」滑稽树前做游戏

2020 年 05 月 06 日

给定一个 $n$ 个点 $m$ 条边的无向图，其中每个点的点权是 $[0;1]$ 范围内生成的连续型随机变量，求：
$\max \{ \max_{i \in V} x_i + \max_{(u,v) \in E} (x_u + x_v) \}$
的期望，答案对 $998244353$ 取模。

$n \leq 25$ 。（实际上可以跑 $n \leq 30$ 。。。

题解

ans = \int_0^2 Pr[\lambda = x] x \text dx = 2 - \int_0^2 Pr[\lambda \leq x] \text dx

考虑如何计算 $Pr[\lambda \leq x]$ ，设 $g(s,y,t)$ 表示对于点集 $s$ ，点权最大值 $\leq y$ ，答案 $\leq t$ 的概率。考虑其状态转义：

如果生成的所有数都 $\leq \frac t 2$ ，则贡献为 $(\frac t 2)^{|s|}$
对于其他情况，考虑最大值点 $i$ ，并递归。

g(s,y,t) = (\tfrac t 2)^{|s|} + \sum_{i \in s} \int_{\tfrac t 2}^y g(s_i, x, t) (t - x)^{|s| - |s_i| - 1}\text dx

其中 $s_i$ 表示从 $s$ 中删除 $i$ 以及所有和 $i$ 相邻的点得到的点集。

如果我们直接暴力状压维护二元多项式转移显然麻烦的一比，而且常数还贼他妈大，考虑理性一点的方式。

首先，如果当前的状态是若干独立的联通块，可以直接把每个联通块的答案相乘，这可以大大减小状态数。

另外，我们可以注意到，对于二元多项式的每一项 $y^i t^j$ ，都满足 $i+j$ 是定值，即二元多项式 $g(s)$ 每项的幂次和都是 $|s|$ 。由二项式定理的系数可以方便得到。

最后，我们需要注意 $g(s,y,t)$ 的取值范围 $\tfrac t 2 \leq y \leq \min(1, t)$ ，所以答案是

ans = 2 - \int_0^1 f(t,t) \text dt - \int_1^2 f(1,t) \text dt

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 30, mod = 998244353, inv2 = (mod + 1) >> 1;
int n, m, tim, G[N], vis[N];
struct z {
  int x;
  z(int x = 0) : x(x) {}
  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; }
} ans, inp[N], inv[N], C[N][N];
unordered_map<int, vector<z>> mp;
inline vector<z> operator*(const vector<z> &a, const vector<z> &b) {
  vector<z> c(a.size() + b.size() - 1);
  for (int i = 0; i < a.size(); i++)
    for (int j = 0; j < b.size(); j++) c[i + j] = c[i + j] + a[i] * b[j];
  return c;
}
inline vector<z> inte(vector<z> f) {
  vector<z> g(f.size() + 1);
  for (int i = 1; i <= f.size(); i++) g[i] = f[i - 1] * inv[i];
  return g;
}
inline z eval(vector<z> a, int l, int r) {
  a = inte(a);
  z p, s;
  int i;
  for (p = 1, i = 0; i < a.size(); i++) s = s + a[i] * p, p = p * r;
  for (p = 1, i = 0; i < a.size(); i++) s = s - a[i] * p, p = p * l;
  return s;
}
void initfac(int n) {
  inp[0] = inv[0] = inv[1] = 1;
  for (int i = 2; i < n; i++) inv[i] = (mod - mod / i) * inv[mod % i];
  for (int i = 1; i < n; i++) inp[i] = inp[i - 1] * inv2;
  for (int i = 0; i < n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
}
int dfs(int u, int s) {
  int res = 1 << u;
  vis[u] = tim;
  for (int v = 0; v < n; v++)
    if (((s >> v) & 1) && ((G[u] >> v) & 1) && vis[v] != tim) res |= dfs(v, s);
  return res;
}
void update(vector<z> &s, vector<z> a, int k) {
  vector<z> b(k + 1);
  for (int i = 0; i <= k; i++) b[i] = C[k][i] * (i & 1 ? mod - 1 : 1);
  a = inte(a * b);
  for (int i = 0; i < a.size(); i++) s[i] = s[i] + a[i], s[0] = s[0] - inp[i] * a[i];
}
vector<z> solve(int s) {
  if (mp.count(s)) return mp[s];
  int l = __builtin_popcount(s);
  vector<z> res;
  vector<int> set;
  for (int t, i = 0; i < n; i++)
    if ((s >> i) & 1) {
      ++tim;
      t = dfs(i, s), s ^= t;
      set.push_back(t);
    }
  for (int x : set) s |= x;
  if (set.size() > 1) {
    res = {1};
    for (auto t : set) res = res * solve(t);
  } else {
    res.resize(l + 1), res[0] = inp[l];
    for (int i = 0; i < n; i++)
      if ((s >> i) & 1) {
        int t = s ^ (s & (G[i] | (1 << i)));
        update(res, solve(t), __builtin_popcount(s & G[i]));
      }
  }
  return mp[s] = res;
}
int main() {
  cin >> n >> m;
  initfac(N), mp[0] = {1};
  for (int u, v, i = 0; i < m; i++) {
    cin >> u >> v, --u, --v;
    G[u] |= 1 << v, G[v] |= 1 << u;
  }
  vector<z> s = solve((1 << n) - 1), a(n + 1);
  for (int i = 0; i < s.size(); i++) a[n] = a[n] + s[i];
  reverse(s.begin(), s.end());
  cout << (2 - eval(s, 1, 2) - eval(a, 0, 1)).x << endl;
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论