Codeforces Deltix Round Summer 2021 F Sports Betting @ Wings            分类 ACM
发布于 星期三, 十月 20 日, 2021 年
更新于 星期四, 十月 21 日, 2021 年

题目

题意

$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) \newline &= (1 - \sum_{S_0 \subset S} P(S_0 \to S-S_0))P(S \to \overline S) \newline &= (1 - \sum_{S_0 \subset S} \frac{P(f(S_0))}{P(S_0 \to \overline S)}) P(S \to \overline S) \newline \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)$. 这应该是最优的解法了.

代码
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;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch