「Summary」CQ 2023 省选前复习记录

伝えに来たよ 傷跡を辿って それなら もう恐れるものはないんだと.

CF449D

看来我确实只会做板题 /kk。
一个很 naive 的想法是定义 $dp_{i, x}$ 表示当前到了第 $i$ 位,与起来的值为 $x$ 的方案数,显然这个做不下去,因为状态数会有重叠,并且这复杂度会爆。
一个不那么 naive 的想法是容斥,定义 $f_i$ 是与值至少为 $i$ 的方案数,$g_i$ 表示恰好,所以有 $g_i = f_i - \sum_{j \& i = i}g_j$ 。因为我们只要 $g_0$ 。

$$ \begin{aligned} ans = g_0 &= f_0 - \sum_{j = 1}^{2^n - 1} g_j \\ &= \sum_{i = 0}^{2^n-1} (-1)^{\mid i \mid} f_i \\ f_i = 2^{s_i} - 1&, s_i = \sum_{j = 1}^{n} [a_j \& i = i] \end{aligned} $$

目标是求 $s_i$ ,记 $cnt_i$ 表示 $i$ 出现的次数。
然后直接对 $cnt$ 进行 $fwt$ 就可以得到 $s_i$ 了。

UOJ266

首先把后续所有的 $xor$ 记为 $+$ 。
记 $f(x)$ 表示以 $x$ 为根的子树的 $SG$ 函数的值, $g(x, y)$ 表示以 $x$ 为根的子树中第一步涂黑了 $y$ 的后的 $SG$ 值,记 $sum(x) = \sum_{y \in x} f(y)$ 。
可以知道 $g(x, y)$ 是子游戏 $x$ 的一个后继局面集合。涂黑了 $z$ 之后相当于从 $z$ 到 $y$ 之间的所有点都会被删去,那么这棵树就会被分成更多个子游戏,那么这些子游戏的 $SG$ 函数的和就是 $f(x)$ ,终止局面是 $g(x, x) = sum(x)$ 。

但是这并不意味着需要把这个链上的所有点都跑一遍,因为已经记录了 $g$ ,具体的转移是

$$ g(x,z) = g(y,z)+\sum\limits_{y'\in son(x), z\notin subtree(y')} f(y') = g(y,z)+(\sum\limits_{y'\in son(x)} f(y'))+f(y)\space\space | \space\space z\in subtree(y) $$

[省选联考 2020 A/B 卷] 冰火战士

第一眼三分,第二眼发现有平台。
继续延续上面这个思路,用 fire 减去 ice 得到一条单调函数,于是我们可以在这个上面二分了。
但是这样是两个 $\log$ 的,发现可以在线段数上二分,但是常数大了,于是改成树状树组倍增很可以过。

[省选联考 2020 A 卷] 组合数问题

需要转下降幂阿,但是我不会,于是学了一下。

$$ \begin{aligned} &\left(\sum\limits_{k=0}^n \sum\limits_{i=0}^m a_i \times k^i\times x^k \times \dbinom{n}{k}\right)\bmod p \\ =&\left(\sum\limits_{k=0}^n \sum\limits_{i=0}^m a_i \times \sum\limits_{j = 0}^i \left\{^i_j\right\} \dbinom{k}{j}j!\times x^k \times \dbinom{n}{k}\right)\bmod p \\ =&\left(\sum\limits_{k=0}^n \sum\limits_{i=0}^m a_i \times \sum\limits_{j = 0}^i \left\{^i_j\right\} \dbinom{n-j}{k-j} \times \dbinom{n}{j}j!\times x^k \right)\bmod p\\ =&\left( \sum\limits_{i=0}^m a_i\sum\limits_{j=0}^i\left\{^i_j\right\}\times\dbinom{n}{j}j!\times \sum\limits_{k=0}^n\dbinom{n-j}{k-j}x^k \right)\bmod p \\ =&\left( \sum\limits_{i=0}^m a_i\sum\limits_{j=0}^i\left\{^i_j\right\}\times\dbinom{n}{j}j!\times (x+1)^{n-j}\times x^j \right)\bmod p \\ =&\left( \sum\limits_{i=0}^m a_i\sum\limits_{j=0}^i\left\{^i_j\right\}\times\frac{n!}{(n-j)!}\times (x+1)^{n-j}\times x^j \right)\bmod p \end{aligned} $$

[省选联考 2020 A 卷] 树

这确实不能直接看穿。

一个比较明显的想法是在知道了子结点的结果后用某种方式迁移到父节点上面。

于是我们需要这样一个玩意儿,对子树内的 $w$ 整体加 $1$ ,插入一个数,合并子树信息。

可以想到 0/1 trie ,插入和合并是平凡的,问题在于这个整体加一怎么做。

首先对于一棵子树,右儿子加一之后变成左儿子,左儿子变成右儿子,但是权值发生改变,具体来说是权值翻倍再异或右儿子权值翻倍。

注意终止结点的标记问题,有一些细节。

贴个代码。

struct Trie {
  int tot, rt[MAXN], nxt[MAXN * MAXM][2], cnt[MAXN * MAXM][MAXM], ed[MAXN * MAXM];
  void insert(int p, int ind, int val) {
    for (int i = 0; i < LIM; i++) {
      int tmp = (val >> i) & 1;
      cnt[ind][i] += tmp;
      if (!nxt[p][tmp]) nxt[p][tmp] = ++tot;
      p = nxt[p][tmp], ed[p]++;
    }
  }
  void update(int p, int ind) {
    for (int i = 0; i < LIM; i++) {
      if (!p) return;
      cnt[ind][i] += ed[nxt[p][0]], cnt[ind][i] -= ed[nxt[p][1]];
      swap(nxt[p][1], nxt[p][0]), p = nxt[p][0];
    }
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    ed[x] += ed[y];
    nxt[x][0] = merge(nxt[x][0], nxt[y][0]);
    nxt[x][1] = merge(nxt[x][1], nxt[y][1]);
    return x;
  }
} trie;

[省选联考 2020 A/B 卷] 信号传递

题面很烦,重新写一下。

$$ \left\{ \begin{aligned} y - x, y > x \\ ky + kx, x \le y \\ \end{aligned} \right. $$

这样我们把整体的贡献拆成每个点的贡献,确切地说,对于最终坐标落在 $x$ 上的点如果存在一条 $x \le y$ ,若 $x \le y$ 则付出 $k$ 的代价,否则付出 $-1$ 的代价。

可以写出这个表达式,但是很抽象,尝试动态分析这个过程,两种贡献方式分开讨论,假设我们有一条传输要求是 $x \rightarrow y$ 。

第一种

$x < y$ ,当 $x$ 出现后,如果 $y$ 在后续的过程中每一次没有出现就会多造成 $1$ 的贡献,于是我们知道他们之间的距离就可以了。意思就是每一对有传输要求的都会在放置一个新的信号塔后产生 $1$ 的贡献。 #### 第二种 $x > y$ ,对比第一种发现是 $x, y$ 之间的距离再加上两倍 $y$ ,那么 $x, y$ 之间的距离可以和第一种一样地去计算,两倍 $y$ 可以在每次加入点的贡献时计算。 代码有点搞人,因为你发现数组开不下,要拆成两个小的集合来做,不知道怎么会搞这个玩意儿。。。 ### [省选联考 2021 A 卷] 矩阵游戏 看起来很简单阿,我直接构造 $a_{i, j} = b_{i - 1, j - 1} - a_{i - 1, j} - a_{i, j - 1} - a_{i - 1, j - 1}$ ,然后看到后面有个限制 $\forall a \le 1e6$ 。 非常明显阿,有较强数量限制的构造,直接上差分约束,调整一下这个式子, $b_{i, j} = a_{i, j} + a_{i + 1, j} + a_{i, j + 1} + a_{i + 1, j + 1}$ 这个是和约束,加入限制 $1 \le a_{i, j} \le 1e6 \Rightarrow 1 \le b_{i, j} - a_{i + 1, j} - a_{i, j + 1} - a_{i + 1, j + 1} \le 1e6$ 。那么对 $a_{i, j}$ 进行调整需要保证这个田字格中的和不变,注意到对每个点限制其实很不好做,并且 $n, m \le 300$ 是常见的行列整体操作的数据范围,马上发现加上这样一个矩阵之后构造依然合法。 $$ \left |\begin{array}{} c_1 + d_1, -c_1 + d_2, c_1 + d_3, -c_1 + d_4 \dots \\ c_2 - d_1, -c_2 - d_2, c_2 - d_3, -c_2 - d_4 \dots \\ c_3 + d_1, -c_3 + d_2, c_3 + d_3, -c_3 + d_4 \dots \\ c_4 - d_1, -c_4 - d_2, c_4 - d_3, -c_4 - d_4 \dots \\ \end{array}\right| $$

现在就好做了,于是我们黑白染色,对于白点 $(i + j) \& 1$ ,$i \rightarrow^{a_{i, j}} j, j \rightarrow^{1e6 - a_{i, j}} i$ ,对于黑点 $!((i + j) \& 1)$ ,$i \rightarrow^{1e6 - a_{i, j}} j, j \rightarrow^{a_{i, j}} i$ 。

跑一边差分约束即可。

[省选联考 2020 A 卷] 作业题

掀起全机房写矩阵树定理狂潮。

看到这个式子很烦阿,起手把这个 $\gcd$ 干掉,熟练地欧拉反演它,拿到的式子是

$$ \begin{aligned} val(T) &= \left( \sum_{i = 1}^{n - 1}w_{e_i} \right) \times \sum_{d \mid \gcd(w_e)} \varphi(d) \\ ans &= \sum_{d} \varphi(d) \times \sum_{T, d \mid w_{e_i}, w_{e_i} \in T} \left( \sum_{i = 1}^{n - 1} w_{e_i} \right) \end{aligned} $$

然后问题是求后面那一块,我们是知道 $\prod_{i = 1}^{n - 1} w_{e_i}$ 怎么求的,这个矩阵树定理就好了,然后大家都说乘积转和是个套路,我不会。

具体是你把 $w_{e_i}$ 换成 $w_{e_i} + 1$ ,然后你乘一下,$(w_1 + 1) \times (w_2 + 1) = (1) + (w_1 w_2) + (w_1 + w_2)$ ,这个式子的一次项就是我们要的东西,然后做完了。