Codeforces Deltix Round Summer 2021 F Sports Betting

$n$ 个点, 点权为 $a_i$. 两点之间有 $\frac{a_i}{a_i + a_j}$ 的概率从点 $i$ 向点 $j$ 连一条有向边(否则即有 $\frac{a_j}{a_i + a_j}$ 的概率 $j \to i$). 即根据概率建一个竞赛图. 求能到达其他所有点的点的期望个数.

$1 \le n \le 14, 1 \le a_i \le 10^6$

点数很少, 所以尝试点集为 $S$, 事件 $f(S)$ 表示有且仅有 $S$ 中的点能到达所有点, 直接根据期望的定义去计算答案, 应该为 $\sum |S|P(f(S))$.

现在考虑 $f(S)$ 如何计算. 首先我们可以发现 $S$ 一定是一个强连通分量, 且有 $\forall x \in S, \forall y \in \overline S, x \to y$ (之后用 $S \to \overline S$ 表示). 简单考虑一下后面这个条件的必要性: 若 $\exists (y \in \overline S, x \in S), y \to x$, 若 $S$ 中有其他点, 则要么 $\exists z \in S, z \ne x, z \to y$, 这种情况 $y$ 能和 $S$ 一起组成 SCC, 与 $f(S)$ 的定义矛盾; 若 $S = \{x\}$, 反过来考虑, 也会有 $x$ 可能与 $y$ 的 SCC 组成 SCC. 与 $f(S)/f(\{x\})$ 矛盾, 若不然, 则仅有 $f(\{y\})$, 与 $f(\{x\})/f(\{x\})$ 矛盾.

点对之间的连边情况是独立的, 所以 $\overline S$ 之间的连边无论怎样也不影响 $f(S)$, 所以 $P(f(S)) = P(S\text{是SCC, 且} S \to \overline S) = P(S\text{是SCC})P(S \to \overline S)$. $P(S \to \overline S)$ 很好算, 先放一边. 考虑 $P(S\text{是SCC})$ 怎么算.

正着很不好做, 考虑做反面, 用 $1$ 减去所有不是 SCC 的连法即可. 什么样的情况不是 SCC 呢? 根据之前的讨论, 若存在 $S_0 \to S-S_0$, 且 $S_0$ 是 SCC, 则 $S$ 不是 SCC. 所以我们枚举 $S_0 \subset S$. 发现可以发现, $(S_0 \to S-S_0) = f(S_0) - (S_0 \to \overline S)$, 所以 $P(S_0 \to S-S_0) = \frac{P(f(S_0))}{P(S_0 \to \overline S)}$

整理一下, 就可以得到

$$\begin{aligned} P(f(S)) &= P(S\text{是SCC})P(S \to \overline S) \\ &= (1 - \sum_{S_0 \subset S} P(S_0 \to S-S_0))P(S \to \overline S) \\ &= (1 - \sum_{S_0 \subset S} \frac{P(f(S_0))}{P(S_0 \to \overline S)}) P(S \to \overline S) \\ \end{aligned}$$

事实上还存在一种等效的写法, 这种写法不需要除法, 复杂度可以少一个逆元的 $\log$.

把上面的式子接着展开:

$$P(f(S)) = P(S_0 \to \overline S) - \sum_{S_0 \subset S} \frac{P(f(S_0))}{P(S_0 \to \overline S)} P(S \to \overline S)$$

后面一项对应的事件其实是: $S_0$ 是 SCC, $S \to \overline S$, $S_0 \to S - S_0$, 这个事件等价于: $S_0$ 是SCC, $S_0 \to \overline {S_0}$, $S_0 \to S - S_0$ $\Longleftrightarrow$ $f(S_0), S_0 \to S - S_0$.

所以可以写成这样:

$$P(f(S)) = P(S_0 \to \overline S) - \sum_{S_0 \subset S} P(f(S_0))P(S_0 \to S - S_0)$$

我们可以通过枚举子集的方法来进行转移 $P(f(S))$, 边界条件是 $P(f(\emptyset)) = 1$. 若 $P(S \to T)$ 暴力算, 那么总复杂度将会是 $O(3^n \cdot n^2)$, 大概 $10^9$, 刚好能过.

其实可以优化, 核心就是预处理 $P(S \to T)$.

一个很显然的思路是预处理 $g(S, T) = P(S \to T)$, 然后在转移的时候 $O(1)$ 调用, 那么转移的复杂度为 $O(3^n)$. 预处理需要枚举两个集合, 时间复杂度是 $O((2^n)^2 \cdot n^2) = O(4^n \cdot n^2)$. 实际上 $S \cap T = \emptyset$, 所以只需要枚举子集, 时间复杂度 $O(3^n \cdot n^2)$, 没变, 笑死, 因为转移实际上就是在枚举子集啊.

预处理其实是想干这么一件事: 用空间换时间. 既然换成 $O(1)$ 对预处理的时间贡献太大(实际上空间复杂度也太高了), 那我换成更大一点的时间, 比如 $O(n)$, 让预处理的时间减小下来. 根据独立事件概率的计算, 设 $w(x, T) = P(\{x\} \to T)$. 那么转移的时候就多一个 $O(n)$, 预处理的复杂度降为 $O(2^n \cdot n^2)$, 总复杂度为 $O(3^n \cdot n + 2^n \cdot n^2 + a) = O(3^n \cdot n + a)$($a$ 是线性预处理逆元).

这里还有一个更妙妙的处理方法. 还是根据独立事件的概率乘积. 既然 $n$ 个对 $n$ 个不行, 就 $\frac{n}{2}$ 个对 $\frac{n}{2}$ 个. 具体来说, 可以开一个数组 $h(0/1, 0/1, S’, T’)$ 表示, $P(S’ \to T’)$, 而第一第二维的 $0/1$ 分别表示的是 $S’$ 和 $T’$ 是"哪一半"或者"哪一个$\frac{n}{2}$“中的点. 这样转移复杂度只会乘上一个常数 $4$, 而预处理的复杂度为 $O(4 \cdot (2^{\frac{n}{2}})^2 \cdot (\frac{n}{2})^2) = O(2^n \cdot n^2)$. 总复杂度为 $O(4 \cdot 3^n + 2^n \cdot n^2 + a) = O(3^n + a)$. 这应该是最优的解法了.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

const int P = 1e9 + 7;
const int MAXN = 20 + 10;
const int MAXS = (1 << 14) + 10;
const int MAXS2 = (1 << 7) + 10;
const int MAXA = 2e6 + 10;

int count(int x) {
  int cnt = 0;
  while (x) {
    cnt++;
    x ^= lowbit(x);
  }
  return cnt;
}

int inv[MAXA];

void init(int n) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= n; i++)
    inv[i] = mult(P - P/i, inv[P%i]);
}

int a[MAXN], n, f[MAXS], ans = 0;
int h[2][2][MAXS2][MAXS2], ALL;

int g(int s, int t) {
  int HALF = ((1 << 7) - 1);
  int sl = s & HALF;
  int sh = s >> 7;
  int tl = t & HALF;
  int th = t >> 7;
  int res = 1;
  res = mult(res, h[1][1][sh][th]);
  res = mult(res, h[1][0][sh][tl]);
  res = mult(res, h[0][1][sl][th]);
  res = mult(res, h[0][0][sl][tl]);
  return res;
}

void calc(int s_is_h, int t_is_h) {
  int HALF = ((1 << 7) - 1);
  int sup = s_is_h ? (ALL >> 7) : min(HALF, ALL);
  int tup = t_is_h ? (ALL >> 7) : min(HALF, ALL);
  for (int s = 0; s <= sup; s++) {
    int s_state = s << (s_is_h ? 7 : 0);
    for (int t = 0; t <= tup; t++) {
      int t_state = t << (t_is_h ? 7 : 0);
      if (s_state & t_state)
        h[s_is_h][t_is_h][s][t] = 0;
      else {
        int &res = h[s_is_h][t_is_h][s][t];
        res = 1;
        for (int i = 0; i < n; i++) if (s_state & (1 << i))
          for (int j = 0; j < n; j++) if (t_state & (1 << j))
            res = mult(res, mult(a[i], inv[a[i]+a[j]]));
      }
    }
  }
}

int main() {
  init(2e6);
  scanf("%d", &n);
  ALL = (1 << n) - 1;
  for (int i = 0; i < n; i++)
    scanf("%d", a + i);
  calc(0, 0); calc(0, 1); calc(1, 0); calc(1, 1);
  for (int s = 1; s <= ALL; s++) {
    int sub = 0, Us = (~s) & ALL;
    for (int s0 = (s-1) & s; s0; s0 = (s0-1) & s) {
      int Ss0 = (~s0) & s;
      sub = pls(sub, mult(f[s0], g(Ss0, Us)));
    }
    f[s] = pls(g(s, Us), -sub);
    ans = pls(ans, mult(f[s], count(s)));
  }
  printf("%d\n", ans);
  return 0;
}