jiangly的博客

博客

The 3rd Universal Cup. Stage 9: Xi'an 题解

2024-09-10 21:31:13 By jiangly

A. An Easy Geometry Problem

Ai=Aiik2,则对于 ir 是好的半径当且仅当 Ai+rAir=b

用线段树或树状数组维护正反两个方向的哈希值,询问时二分长度然后比较哈希值即可。

时间复杂度 O(n+qlog2n)

B. Counting Multisets

考虑 p(S) 是奇数的条件,设 cnt(x)xS 中的出现次数,则 p(S)=n!xcnt(x)!。根据 Lucas 定理,p(S) 是奇数当且仅当所有 cnt(x) 在二进制下相加没有进位。因此,合法的可重集就是对于 n 的二进制中每个 2i,任意选择一个 x 重复 2i 次。

现在还要解决 ORxSx=y 的条件。可以通过容斥将条件改写为 xS,bin(x)bin(y)x 的二进制中的 1y 的子集)。

因此,对于固定的 y,只需要计算对于每个 2ibin(n),2jbin(y),可以选或不选 2i+j,总和等于 x 的方案数。这可以通过数位 DP 解决,即 f(i,j) 表示确定最低 i 位,目前进位为 j 的方案数,时间复杂度 O(logxlognpcnt(y))

总时间复杂度 O(2pcnt(y)pcnt(y)logxlogn)

C. Counting Strings

(复读官方题解)

首先把条件改写成 gcd(r,rl)=1。建出 SAM,对于每个 rl,假设保留所有 gcd(r,rl)=1r 对应的结点,这样的串的个数就是这些结点到根的路径的并中深度为 rl 的点数。如果我们把这些结点按 DFS 序排序,则容易维护这些路径的并。

考虑通过搜索枚举 rl 包含质因子的集合来优化这个算法。在加入一个素数 p 时,要删除所有 prr 对应的结点,这样的删除对路径并的变化是删除一条链,可以用链表维护前驱后继,求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案,我们维护每个深度的点数,修改的影响是区间加,查询是单点求值,可以用 O(1) 修改 O(n) 查询的分块维护。

接下来只需要分析这样搜索时需要修改的次数 F(n)。实测在 n=105 时,修改的次数不超过 2107。具体的分析是,修改次数等于 n1x=1[μ(x)0]nmaxp(x),其中 maxp(x)x 的最大素因子。

时间复杂度 O(F(n)+nn)

D. Bracket Sequence

考虑 DP 计算一个给定字符串 s 的方案数。f(i,j) 表示 S[0:i] 中等于 ()[0:j] 的子序列的方案数,则答案就是 f(|s|,2k)

K=max{k}。对于第 1 类区间询问,我们可以把这个 DP 写成 vMlMl+1Mr,其中 Misi 的转移矩阵。由于矩阵的特殊性质,可以在 O(K2) 的时间内计算一个矩阵乘上 Mi,因此只需要预处理 M1M2Mi(M1M2Mi)1,就可以在 O(K) 时间内回答一个询问。

对于第 2 类区间询问,首先可以添加一个 DP 状态,表示还没有进入子串,同时预处理 M1M2Mi 的前缀和即可。

总时间复杂度 O(nK2+qK)

E. Dominating Point

S(u)={v(u,v)Eu=v}。点 u 是支配点当且仅当不存在 vu 满足 S(u)S(v)

把所有点按度数从大到小排序,依次检查是否存在这样的 v。显然我们只需要检查已经确定是支配点的 v,而找到三个支配点后就可以直接返回,因此对于每个 u 只需检查 O(1) 个点,每次检查 O(n)

总时间复杂度 O(n2)

F. An Easy Counting Problem

因为 p 是素数,由 Lucas 定理可知组合数是 p 进制下每一位组合数的乘积。0ba<p 的组合数分布可以 O(p2) 暴力计算。

求出一位的组合数分布后,我们要计算其在 i,jijmodp 卷积意义下的 k 次幂。通过找一个原根并将下标取离散对数的变换,我们可以将其转化为普通的循环卷积,可以用 FFT 优化。

时间复杂度 O(p2+plogplogk)

G. An Easy Math Problem

我们加上 gcd(p,q)=1 的限制,不同的 (p,q) 就对应了不同的 r。考虑计算这样的 (p,q) 的方案数。显然方案数是积性的,即每个素数独立,且 pk 的方案数是 2k+1(1,1),(pi,1),(1,pi))。分解 n 之后直接计算即可。

可以预处理素数来加速分解,时间复杂度 O(\sqrt N+q\frac{\sqrt N}{\log N})

H. Elimination Series Once More

我们对每个 i,和每个 j=1,2,\ldots,n,来计算 i 能不能赢下第 j 轮,也就是能不能让 a_i 变成其所在的大小为 2^j 的子树的最大值。

只需要判断两个条件:

  • 所在子树中大于 a_i 的不超过 k 个。每次最多只能把一个换出去。
  • a_i\ge 2^j。这是为了保证有足够多小的数放进子树。

这个条件可以在归并排序的过程中快速判断,时间复杂度 O(n2^n)

I. Max GCD

我们枚举 \gcd=d,看是否能用 d 的倍数满足条件。显然对于固定的 ji 应该越大越好,k 在满足 k-j\ge j-i 的前提下越小越好。

考虑从大到小枚举 j,找到对应的 iki 可以直接找到,但 k 并不单调。然而如果 i 更小的时候 k 更大,这样的三元组一定是不优的,因此仍然是只需要让 k 单调下降。令 A=\max\{a_i\}d(A)1A 中约数个数的最大值,则可以在 O(nd(A)) 的时间中找到所有的三元组。

询问就是简单的二维偏序,为了平衡复杂度,可以使用 O(1) 修改、O(\sqrt n) 查询的分块,总时间复杂度 O(nd(A)+q\sqrt n)

J. Graph Changing

考虑在 G_1 中,两点有边当且仅当 |u,v|\ge k,如果 u,v 可达,则最短路径长度一定不超过 3u\to 1\to n\to v)。因此如果 k>3G_2 开始就是空图。

k=3 时,显然当 n 足够大时 G_2 开始也是空图。

k=2 时,显然当 n 足够大时 G_{i+1}G_i 的反图。

k=1 时,显然 G_1 开始就是完全图。

因此只需要预处理 n 小的情况(例如 n< 10),特判 k=1,2,3,剩余的情况分类讨论答案是 1,2,3 即可。

K. Penguins in Refrigerator

先求方案数,考虑从大到小插入数。首先大于 M/2 的数相对顺序不改变,对于不超过 M/2 的每个数 a_i,找到左右第一个大于 M-a_i 的数,则 a_i 只能插入到这个区间中。注意到这些区间形成一棵树形结构,因此方案数就是每个数插入的方案数相乘。

再求字典序最小的方案数。大于 M/2 的数相对顺序不改变,可以连一条链。对于不超过,对于不超过 M/2 的每个数 a_i,找到左右第一个大于 M-a_i 的数,只需要它们之间的相对顺序不改变即可(因为其他的顺序关系都通过链确定了)。之后用堆维护,求字典序最小的拓扑排序即可。

时间复杂度 O(n\log n)

L. Prism Palace

所求的就是随机旋转一个角度,有一条边在 y 轴上的投影是整个凸包的概率。对于相邻的两个内角 a,b,这条边满足条件的角度范围是 \max\{0,\pi-a-b\}。对这些角度求和然后除以 2\pi 即可。时间复杂度 O(n)

M. Random Variables

考虑对每个 k 计算每种数出现次数不超过 k 的方案数。其等于 n![x^n]\left(\sum_{i=0}^k\frac{x^i}{i!}\right)^m 注意由于模数不一定是素数,所以不一定有阶乘逆元,但 EGF 的卷积只需要乘上组合数。

考虑容斥,即把 \sum_{i=0}^k\frac{x^i}{i!} 写成 e^x-\sum_{i=k+1}^\infty \frac{x^i}{i!}。如果能够预处理所有 \left(\sum_{i=k}^\infty \frac{x^i}{i!}\right)^m,就能够在 O(n^2\log n) 时间内计算答案(因为 mk\le n)。

这里 m 的范围是 \frac{n}{k},按照 k 从大到小预处理,每次只需给内部的式子加上一项,展开后是 O(m) 项已知的式子求和。因此可以在 O\left(\sum_{k=1}^n \frac{n^3}{k^2}\right)=O(n^3) 时间内预处理所有的值。对于每组数据,还要对 0\le i\le n 计算 m\choose i,可以通过快速幂计算 (1+x)^m\bmod x^{n+1}O(n^2\log m) 的时间内计算。因此总复杂度是 O(N^3+\sum n^2(\log n+\log m))

对于整数 B,我们只预处理 k\ge B 的值,复杂度是 O\left(\frac{n^3}{B}\right)。对于 k< B,我们要计算的是一个短多项式的幂,可以通过 ODE(f'g=mg'f)来计算,注意 EGF 的求导就是移位,所以不需要除法,复杂度是 O(nk)。总时间复杂度 O\left(\frac{N^3}{B}+\sum n B^2+\sum n^2(\log n+\log m)\right)

官方题解里有 O(\sum n^2\log n) 的做法。

N. Python Program

外层循环直接模拟,内层循环用等差数列求和。

时间复杂度 O(|a-b|)

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。