A - 打字练习

出题：memset0

送分模拟题，按题意模拟即可。

需要注意的是对退格键的判断，如果光标已经在行首，则直接忽略被读入的退格键。

B - 小猪佩奇爬树

出题：_QAQ

维护所有相同节点颜色的链并，若不构成一条链则显然答案为 00 。

若仅包含 11 个节点，则枚举所有子树大小进行统计。

否则即为链的 22 个端点所对子树大小的乘积。

C - 小猪佩奇玩游戏

出题：_QAQ & SPJ：memset0

容易发现可以将 {1,2,…,n}\{1,2,\dots,n\} 进行分组，不同组别的答案是独立的。

举个栗子，对于 {1,2,3,4,5,6,7,8,9}\{1,2,3,4,5,6,7,8,9\} ，可以将数字分为 {1},{3,9},{2,4,8},{5},{6},{7}\{1\},\{3,9\},\{2,4,8\},\{5\},\{6\},\{7\}

容易发现这些组别之间互不干扰且互不影响，所以只需要计算每个组别独立的期望值并进行相加即可

那么最终答案即为

∑i=1∞fi×gi \sum_{i=1}^{\infty} f_i \times g_i

其中 fif_i 表示大小为 ii 的组别个数, gig_i 表示大小为 ii 的组别期望删除多少次,我们分别来计算

先来计算 fif_i ,显然大小至少为 ii 的组别个数为 ni\sqrt[i]{n}

对于 11 个大小为 xx 的组别，其为在大小为 yy 的组别中出现 ⌊xy⌋\lfloor \frac{x}{y} \rfloor ，所以可以考虑直接容斥计算，复杂度为 O(log⁡n2)O(\log n^2)

显然 ii 最多只能取到 log⁡n\log n ，所以 fif_i 便很轻松地算出来了

考虑怎么算 gig_i ，其实等价于给定数列 {1,2,…,i}\{1,2,\dots,i\} ，每次删除 11 个数及其倍数

我们考虑一个等价类问题，枚举所有关于 ii 的排列， xx 会产生贡献当且仅当 xx 的前面没有 xx 的因子，那么根据概率的独立性， xx 产生贡献的概率为 1σ(x)\frac{1}{\sigma(x)} ，因此有

gi=∑x=1i1σ(x) g_i=\sum_{x=1}^i \frac{1}{\sigma(x)}

总复杂度为 O(Tlog⁡2n)O(T \log^2 n)

D - 赛车游戏

出题：memset0

一道有意思的图论题。

对于一个点 uu ，若不存在 1→u1 \rightarrow u 的路径或 u→nu \rightarrow n 的路径，那么这个点对答案没有影响，可以直接忽略。

剩下的图一定是一个 DAG。因为如果有环，必定可以形成多条起点到终点的路径，使得无解。

考虑如何给一个 DAG 赋边权：由于每条 1→n1 \rightarrow n 的路径长度是相同的，那么每条 1→i (i∈[1,n])1 \rightarrow i\ (i \in [1,n]) 的路径长度也是相同的。设为 disidis_i ，跑差分约束即可。

时间复杂度即 SPFA 的时间复杂度 O(nm)O(nm) ，实际上常数因子非常小。

此题的思路和代码都非常清新，只是 SPJ 和构造数据非常恶心，出题人表示体验极差。

E - 小猪佩奇学数学

出题：_QAQ

原式等价于

∑i=0n(ni)×pi×i−i mod kk mod 998244353 \sum_{i=0}^n \binom n i \times p^{i} \times \frac{i-i\bmod k}{k} \bmod 998244353

即

∑i=0n(ni)×pi×ik−∑i=0n(ni)×pi×i mod kk mod 998244353 \sum_{i=0}^n \binom n i \times p^{i} \times \frac{i}{k} -\sum_{i=0}^n \binom n i \times p^{i} \times \frac{i \bmod k}{k}\bmod 998244353

考虑前半部分式子

∑i=0n(ni)×pi×ik \sum_{i=0}^n \binom n i \times p^{i} \times \frac{i}{k}

根据

mn(nm)=(n−1m−1) \frac{m}{n}\binom n m = \binom {n-1} {m-1}

所以该式子等价于

1kn∑i=1n(n−1i−1)×pi \frac{1}{kn} \sum_{i=1}^n \binom {n-1} {i-1} \times p^{i}

即

pkn∑i=0n−1(n−1i)×pi−1×1n−i \frac{p}{kn} \sum_{i=0}^{n-1} \binom {n-1} {i} \times p^{i-1} \times 1^{n-i}

根据二项式定理，即

pkn(p+1)n−1 \frac{p}{kn}(p+1)^{n-1}

对于后半部分式子容易发现 k≤220k \leq 2^{20} ，显然的思路是将数字按照对 kk 的模数进行讨论

1k∑i=0n(ni)×pi×(i mod k) mod 998244353 \frac{1}{k}\sum_{i=0}^n \binom n i \times p^{i} \times (i \bmod k) \bmod 998244353

即

1k∑t=0k−1t∑i=0n(ni)×pi×[i mod k=t] mod 998244353 \frac{1}{k}\sum_{t=0}^{k-1} t\sum_{i=0}^n \binom n i \times p^{i} \times [i \bmod k = t] \bmod 998244353

由单位根反演

[i mod k=t]=1k∑c=0k−1wk(i−t)×c [i\ mod\ k = t]=\frac{1}{k}\sum_{c=0}^{k-1} w_k^{(i-t) \times c}

代入原式，有

1k∑t=0k−1t∑i=0n1k∑c=0k−1wk(i−t)×c(ni)×pi mod 998244353 \frac{1}{k}\sum_{t=0}^{k-1} t\sum_{i=0}^n \frac{1}{k}\sum_{c=0}^{k-1} w_k^{(i-t) \times c}\binom n i \times p^{i} \bmod 998244353

即

1k2∑t=0k−1t∑c=0k−1wk−t×c∑i=0n(ni)wki×c×pi mod 998244353 \frac{1}{k^2}\sum_{t=0}^{k-1} t\sum_{c=0}^{k-1}w_k^{-t \times c}\sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i} \bmod 998244353

发现后半部分很像二项式定理，即

∑i=0n(ni)wki×c×pi=∑i=0n(ni)wki×c×pi×1n−i=(wkcp+1)n \sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i}=\sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i} \times 1^{n-i}=(w_k^cp+1)^n

那么原式等价于

1k2∑t=0k−1t∑c=0k−1wk−t×c(wkcp+1)n mod 998244353 \frac{1}{k^2}\sum_{t=0}^{k-1} t\sum_{c=0}^{k-1}w_k^{-t \times c} (w_k^cp+1)^n \bmod 998244353

发现后半部分为关于 wk−tw_k^{-t} 的 k−1k-1 次多项式，可以暴力多项式插值，但是这样太慢了

类似我们考虑将 wktcw_k^{tc} 看作 wk(t+c2)−(t2)−(c2)w_k^{\binom {t+c}{2}-\binom t 2 - \binom c 2}

那么原式等价于

1k2∑t=0k−1tc∑c=0k−1wk−(t+c2)+(t2)+(c2)(wkcp+1)n mod 998244353 \frac{1}{k^2}\sum_{t=0}^{k-1} t^c\sum_{c=0}^{k-1}w_k^{-\binom {t+c}{2}+\binom t 2+\binom c 2} (w_k^cp+1)^n \bmod 998244353

可以看作卷积的形式，那么只需要一次 NTT 就可以带走了，复杂度为 O(klog⁡k+klog⁡n)O(k \log k+k \log n)

F - 美德的讲坛

出题：Isonan

算法1

我会爆搜！

复杂度 O(2nq)O(2^nq) ，期望得分 20′20' 。

算法2

设 xx 的最高位为 mxmx ，即 mx∈N,2mx≤x<xmx+1mx\in \mathbb{N},2^{mx}\le x < x^{mx+1} 。

我们把 aia_i 按照 ⌊ai2mx⌋\lfloor{a_i\over 2^{mx}}\rfloor 分组。

容易发现组内两两异或和都是 <x< x 的。

对于 x=2k,k∈Nx=2^k,k\in \mathbb{N} 的部分分，我们发现分完组以后跨组的异或和全是 ≥x\ge x 的。

我们只要找到最大的组输出就行了。

复杂度 O(n+q)O(n+q) ，期望得分 20′20' 。

算法3

对于一般情况，我们发现相邻组之间是有可能产生 <x< x 的异或和的。

那么我们的问题变成了：

现在有两组点，左边每个点有一个权值 aia_i ，右边每个点有一个权值 bib_i 。现在要在左右各选出一些点，使得两两异或和 <x< x 。

我们发现这个东东有点二分图的味道。那么是不是可以网络流呢？！

我们用如下方法建图：

源点向左边所有点连边，流量为 11 。

当 ai⊕bj≥xa_i\oplus b_j\ge x 时，左边点 ii 向右边 jj 连边，流量为 ∞\infty 。

右边所有点向汇点连边，流量为 11 。

我们考虑这个图的最小割的意义。

如果 ai⊕bj≥xa_i\oplus b_j\ge x ，那么 i,ji,j 之中必定要删掉一个。一个割表示的就是一个删除一些数字，使得剩下数字两两异或和均 <x< x 的方案。

那么我们要求的就是总点数-最小割。

复杂度 O(n2q)O(n^2q) ，期望得分 30′30' 。

算法4

我们发现连边可以用 trietrie 树优化。

复杂度 O(nnlognq)O(n\sqrt{n}lognq) ，实现得好能得 50′50' 。

（不是很会分析复杂度，大概是这样吧）

算法5

由于最大流=最小割，我们考虑从最大流的角度入手。

我们发现这个图的最大流也就是保留 ai⊕bj≥xa_i\oplus b_j\ge x 的边时，该二分图的最大匹配。

我们可以把这个问题搬到 trietrie 树上解决。

把所有数丢到 trietrie 树上。

设 solve(a,b,dep)solve(a,b,dep) 为 trietrie 树上以 a,ba,b 为根的子树之间进行匹配，两棵子树的最大深度均为 depdep 。

以下用 a0,a1,b0,b1a0,a1,b0,b1 表示 a/ba/b 的左 // 右子树，用 ∣a∣|a| 表示 aa 中点数。

当 xx 在 depdep 这一位上是 11 时，只有 a0a0 和 b1b1 ， a1a1 和 b0b0 可以匹配。

此时答案就是 solve(a0,b1,dep−1)+solve(a1,b0,dep−1)solve(a0,b1,dep-1)+solve(a1,b0,dep-1) 。

当 xx 在 depdep 这一位上时 00 时， a0a0 和 b1b1 ， a1a1 和 b0b0 一定可以匹配。

当

∣a0∣<∣b1∣∣a1∣<∣b0∣ |a0| < |b1|\\ |a1| < |b0|

或

∣a0∣>∣b1∣∣a1∣>∣b0∣ |a0|>|b1|\\ |a1|>|b0|

时，答案显然是 min⁡(∣a∣,∣b∣)\min(|a|,|b|) 。

否则，以

∣a0∣<∣b1∣∣a1∣>∣b0∣ |a0| < |b1|\\ |a1|>|b0|

为例。

我们发现我们只需要额外考虑 a1a1 和 b1b1 的匹配。

答案即为 min⁡(solve(a1,b1,dep−1),b1−a0,a1−b0)+a0+b0\min(solve(a1,b1,dep-1),b1-a0,a1-b0)+a0+b0 。

这样基本就做完了。

我们发现单次修改的时候只会有 loglog 个节点被改动，每次只要把这些位置上的 solvesolve 重新计算就好了。可以类似记搜解决。

复杂度 O((n+q)log⁡2V)O((n+q)\log ^2V) ，期望得分 100′100' 。

转载于LGR60 洛谷 10 月月赛 I 讲评