Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客

2021 ICPC 陕西省赛 补题

Wings  收录于  类别 ACM
     约 2569 字  预计阅读 6 分钟    次阅读     条评论  

《没 人 会 数 论》

从区间 $[l, r]$ 中选 $k$ 个数求 gcd, 问不同结果的个数

$1 \le l, r, k \le 10^{12}, 2 \le k, r - l + 1$

推一下式子, 假设 gcd 是 $x$, 那么只要满足:

$$\left\lfloor\frac{r}{x}\right\rfloor - \left\lceil\frac{l}{x}\right\rceil \ge k$$

那么这个 $x$ 就是可行的, 对答案贡献 +1.

把上取整转换成下取整, 然后两个数论分块做一下, 再遍历统计答案就行了. 具体看代码.

对, 就这么简单, 考场因为没人会数论分块而没做出来…

 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

int T = 1, n;
LL L, R, k, ans = 0;

typedef vector<pair<LL, LL>> VPLL;
VPLL block_div(LL x) {
  VPLL v;
  for (LL l = 1, r; l <= x; l = r + 1) {
    r = x / (x / l);
    v.emplace_back(r, x / l);
  }
  return v;
}

int main() {
  while (T--) {
    scanf("%lld%lld%lld", &L, &R, &k);
    VPLL vr = block_div(R);
    VPLL vl = block_div(L-1);
    vr.emplace_back(INF, 0);
    vl.emplace_back(INF, 0);
    LL last = 0;
    for (auto it_r = vr.begin(), it_l = vl.begin(); it_r != vr.end() || it_l != vl.end(); ) {
      auto[rr, rv] = *it_r;
      auto[lr, lv] = *it_l;
      ans += (LL) (rv - lv >= k) * (min(rr, lr) - last);
      if (rr >= lr)
        it_l++;
      if (lr >= rr)
        it_r++;
      last = min(rr, lr);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

n 个点的树, 点权 $z_u = \frac{p_u}{q_u}$, 边权 $w_{uv} = \frac{a_{uv}}{b_{uv}}}$. 初始点全为白色. 每个点有点权的概率自己变为黑色, 若相邻点为黑色, 则有边权的概率被感染成黑色. 定义 “水平” 为最浅的被感染的点的深度. 求 “水平” 的期望.

$1 \le n \le 10^5, 0 \le p, q, a, b \le 10^6$

这题没做出来是我的问题, 对概率论的应用还不熟. 虽然想到了, 状态里不包含从上往下感染的概率, 但是还是没搞出来. 主要是因为两点:

  1. 没有反过来考虑.

考场一直定义的是变成黑色. 这样会造成 自己变 和 被感染变 的 并集, 而并集的概率不是简单的相加. 在处理这个问题的时候, 我用的是条件概率, 想加上条件来达到计算的效果, 但是这样一来就极度复杂了.

  1. 没用的条件不需要上条件概率.

在想后期望怎么算的时候, 又去想不被上面感染的概率了. 想把它公式化出来, 结果是更加更加复杂. 因为上面的 在题目的情景下永远是白色, 所以 不存在被上面感染, 也就更不用把它算出来了.

好了, 现在针对上面两点, 重新做一遍这个题.

首先, 由于 “水平” 的定义, 某一层往上的点都是白色的, 而这一层至少一个黑色. 那么, 这个黑色永远不会是被上面的感染, 所以我们不需要考虑被上面感染的情况 (自然不用考虑被上面感染的概率, 或者被上面感染的条件).

假如设 $dp(u)$ 为 $u$ 因为自己或者儿子变黑的概率. 这样的话, 状态转移是 并, 比较麻烦, 考虑取反, 变成 且, 且 只用乘法就行, 更加方便.

所以, 设 $dp(u)$ 为 $u$ 自己不变黑, 且不被儿子感染成黑的概率. 转移方程:

$$dp(u) = (1 - z_u) \prod_{v \in SON(u)} (dp(v) + (1 - dp(v))(1-w_{uv}))$$

即, $u$ 是白色的概率为, 自己不变, 而且对所有儿子 $v$ 来说, 要么 $v$ 是白色, 要么 $v$ 是黑色但是不感染 $u$.

接下来计算 “水平” 的期望.

可以把整棵树分成三部分, 这一层全白, 下一层至少一个黑, 上面全白.

上面全白很好算, 由于这一层全白, 所以没有向上感染的概率, 于是上面全白就是所有点自己不变的概率相乘.

这一层全白要单独抽出来, 因为在我们定义的 $dp$ 意义下, 是和下一层有黑的有联系的. 所以并不是简单的 $\prod dp(u)$. 这两部分的概率应该这样算:

$$P(\text{这一层全白}|\text{下一层至少一个黑})P(\text{下一层至少一个黑})$$

简单的 $\prod dp(u)$ 的概率其实是 $P(\text{这一层全白})$. 那么根据全条件概率, 可以得到:

$$\begin{aligned} P(\text{这一层全白}) &= P(\text{这一层全白}|\text{下一层至少一个黑})P(\text{下一层至少一个黑}) \newline &+ P(\text{这一层全白}|\text{下一层全白})P(\text{下一层全白}) \end{aligned}$$

$P(\text{这一层全白}|\text{下一层全白})$ 这个东西其实很好算, 因为下一层全白, 那么这一层全白就是这一层的点都自己不变. 即 $P(\text{这一层全白}|\text{下一层全白}) = \prod (1 - z_u)$

所以就有

$$\begin{aligned} &P(\text{这一层全白}|\text{下一层至少一个黑})P(\text{下一层至少一个黑}) \newline = &P(\text{这一层全白}) - P(\text{这一层全白}|\text{下一层全白}) \newline = &\prod dp(u) - \prod (1 - z_u) \prod dp(v) \end{aligned}$$

设 $f(d) = \prod_{u \in DEP(d)} dp(u)$, $g(d) = \prod_{u \in DEP(d)} (1 - z_u)$, 有

$$\begin{aligned} &P(\text{这一层全白}|\text{下一层至少一个黑})P(\text{下一层至少一个黑}) \newline = &P(\text{这一层全白}) - P(\text{这一层全白}|\text{下一层全白}) \newline = &\prod dp(u) - \prod (1 - z_u) \prod dp(v) \newline = &f(d) - g(d)f(d+1) \end{aligned}$$

现在只差乘上一个 $P(\text{上面全白}) = \prod (1 - z_u) = \prod_{k = 1}^{d - 1}g(k)$ 了. 令 $h(d)$ 为 $g(d)$ 的前缀积, 则这玩意就等于 $h(d-1)$ 了.

然后根据期望的定义, 答案就是:

$$\sum_{d=0}^{mxd-1} h(d-1)\left[f(d) - g(d)f(d+1)\right](d+1)$$

注意一下边界, $h(0) = h(-1) = 1$, $h(-1)$ 没办法直接在数组中表示, 可以先算第一层, 也就是根, 再循环算剩下的.

复杂度 $O(n + MAXA)$ (线性逆元比 $n$ 大, 笑死)

 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

int T = 1, n, z[MAXN], f[MAXN], g[MAXN], h[MAXN];
vector<PII> G[MAXN];

int dp[MAXN], mxd = 0, ans = 0;
VI dep[MAXN];

void dfs(int u, int f, int d) {
  mxd = max(mxd, d);
  dep[d].emplace_back(u);
  dp[u] = 1 - z[u];
  for (auto[v, w] : G[u]) if (v != f) {
    dfs(v, u, d + 1);
    dp[u] = mult(dp[u], pls(dp[v], mult(1 - dp[v], 1 - w)));

  }
}

int main() {
  init_liner_inverse(1000000);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      z[i] = mult(x, inv[y]);
    }
    for (int i = 1; i < n; i++) {
      int u, v, x, y;
      scanf("%d%d%d%d", &u, &v, &x, &y);
      int tmp = mult(x, inv[y]);
      G[u].emplace_back(v, tmp);
      G[v].emplace_back(u, tmp);
    }
    dfs(1, 0, 1);
    h[0] = 1;
    for (int d = 1; d <= mxd; d++) {
      f[d] = g[d] = 1;
      for (auto u : dep[d]) {
        f[d] = mult(f[d], dp[u]);
        g[d] = mult(g[d], 1 - z[u]);
      }
      h[d] = mult(h[d-1], g[d]);
    }
    ans = mult(1 - f[1], 1);
    for (int d = 1; d < mxd; d++)
      ans = pls(ans, mult(mult(h[d-1], f[d] - mult(g[d], f[d+1])), d+1));
    printf("%d\n", ans);
  }
  return 0;
}

构造一个大小为 $n$ 的不可重正整数集合, 要求任意删除一个元素, 都能够将剩余元素划分成两个和相等的集合. 给出构造方案和删除每个元素的划分方案.

$1 \le n \le 2000$

我人傻了. 规律很好找, 就奇数序列, 长度为大于 $5$ 的奇数. 考场构造没构造出来. 想着这构造方案应该很多, 就没写暴力找规律. 结果, 非常朴素的暴力跑的贼快.

教训就是, 下次先写暴力.

看完题解后, 总结一下这种构造要怎么想.

首先, 分成两个和相等的集合, 可以看成给每个元素分配正负号 (去年多校有个题也是这样考虑的, 又忘了, md), 然后相邻元素做差是 $2$. 根据符号的不同, 可以构造 $2$ 和 $-2$. 于是乎这一步转换成给 $2$ 分配正负号. 如果恰好偶数个 $2$, 也就是可能 $4n$ 个元素 (加上一个删除的就是 $4n+1$), 就正好可以分组. 那再考虑 $4n+3$, 这样会有奇数个 $2$. 可以将 $1+3$ 看成 $4$ 就比原来的 $3-1 = 2$ 多一个 $2$, 凑到偶数. 删除了 $1, 3$ 等情况的再特殊讨论, 高度总结一下就是用最少的前缀去构造满足和为 $0$ 的条件, 这样后缀可以用相邻做差的方法使其和为 $0$.

构造写炸了, xs. 码力不够, 或者说写代码的逻辑结构还不是特别清晰. 这东西难练.

更新于 2022-07-11
 ICPC
返回 | 主页