2021 ICPC 陕西省赛 补题

注意
本文最后更新于 2022-07-11,文中内容可能已过时。

《没 人 会 数 论》

从区间 $[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. 码力不够, 或者说写代码的逻辑结构还不是特别清晰. 这东西难练.