A. An Easy Geometry Problem
令 A′i=Ai−i⋅k2,则对于 i,r 是好的半径当且仅当 A′i+r−A′i−r=b。
用线段树或树状数组维护正反两个方向的哈希值,询问时二分长度然后比较哈希值即可。
时间复杂度 O(n+qlog2n)。
B. Counting Multisets
考虑 p(S) 是奇数的条件,设 cnt(x) 是 x 在 S 中的出现次数,则 p(S)=n!∏xcnt(x)!。根据 Lucas 定理,p(S) 是奇数当且仅当所有 cnt(x) 在二进制下相加没有进位。因此,合法的可重集就是对于 n 的二进制中每个 2i,任意选择一个 x 重复 2i 次。
现在还要解决 ORx∈Sx=y 的条件。可以通过容斥将条件改写为 ∀x∈S,bin(x)⊂bin(y)(x 的二进制中的 1 是 y 的子集)。
因此,对于固定的 y,只需要计算对于每个 2i∈bin(n),2j∈bin(y),可以选或不选 2i+j,总和等于 x 的方案数。这可以通过数位 DP 解决,即 f(i,j) 表示确定最低 i 位,目前进位为 j 的方案数,时间复杂度 O(logxlogn⋅pcnt(y))。
总时间复杂度 O(2pcnt(y)pcnt(y)logxlogn)。
C. Counting Strings
(复读官方题解)
首先把条件改写成 gcd(r,r−l)=1。建出 SAM,对于每个 r−l,假设保留所有 gcd(r,r−l)=1 的 r 对应的结点,这样的串的个数就是这些结点到根的路径的并中深度为 r−l 的点数。如果我们把这些结点按 DFS 序排序,则容易维护这些路径的并。
考虑通过搜索枚举 r−l 包含质因子的集合来优化这个算法。在加入一个素数 p 时,要删除所有 p∣r 的 r 对应的结点,这样的删除对路径并的变化是删除一条链,可以用链表维护前驱后继,求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案,我们维护每个深度的点数,修改的影响是区间加,查询是单点求值,可以用 O(1) 修改 O(√n) 查询的分块维护。
接下来只需要分析这样搜索时需要修改的次数 F(n)。实测在 n=105 时,修改的次数不超过 2⋅107。具体的分析是,修改次数等于 ∑n−1x=1[μ(x)≠0]nmaxp(x),其中 maxp(x) 是 x 的最大素因子。
时间复杂度 O(F(n)+n√n)。
D. Bracket Sequence
考虑 DP 计算一个给定字符串 s 的方案数。f(i,j) 表示 S[0:i] 中等于 ()∞[0:j] 的子序列的方案数,则答案就是 f(|s|,2k)。
令 K=max{k}。对于第 1 类区间询问,我们可以把这个 DP 写成 v⋅MlMl+1⋯Mr,其中 Mi 是 si 的转移矩阵。由于矩阵的特殊性质,可以在 O(K2) 的时间内计算一个矩阵乘上 Mi,因此只需要预处理 M1M2⋯Mi 和 (M1M2⋯Mi)−1,就可以在 O(K) 时间内回答一个询问。
对于第 2 类区间询问,首先可以添加一个 DP 状态,表示还没有进入子串,同时预处理 M1M2⋯Mi 的前缀和即可。
总时间复杂度 O(nK2+qK)。
E. Dominating Point
令 S(u)={v∣(u,v)∈E∨u=v}。点 u 是支配点当且仅当不存在 v≠u 满足 S(u)⊂S(v)。
把所有点按度数从大到小排序,依次检查是否存在这样的 v。显然我们只需要检查已经确定是支配点的 v,而找到三个支配点后就可以直接返回,因此对于每个 u 只需检查 O(1) 个点,每次检查 O(n)。
总时间复杂度 O(n2)。
F. An Easy Counting Problem
因为 p 是素数,由 Lucas 定理可知组合数是 p 进制下每一位组合数的乘积。0≤b≤a<p 的组合数分布可以 O(p2) 暴力计算。
求出一位的组合数分布后,我们要计算其在 i,j→i⋅jmodp 卷积意义下的 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(√N+q√NlogN)。
H. Elimination Series Once More
我们对每个 i,和每个 j=1,2,…,n,来计算 i 能不能赢下第 j 轮,也就是能不能让 ai 变成其所在的大小为 2j 的子树的最大值。
只需要判断两个条件:
- 所在子树中大于 ai 的不超过 k 个。每次最多只能把一个换出去。
- ai≥2j。这是为了保证有足够多小的数放进子树。
这个条件可以在归并排序的过程中快速判断,时间复杂度 O(n2n)。
I. Max GCD
我们枚举 gcd=d,看是否能用 d 的倍数满足条件。显然对于固定的 j,i 应该越大越好,k 在满足 k−j≥j−i 的前提下越小越好。
考虑从大到小枚举 j,找到对应的 i 和 k。i 可以直接找到,但 k 并不单调。然而如果 i 更小的时候 k 更大,这样的三元组一定是不优的,因此仍然是只需要让 k 单调下降。令 A=max{ai},d(A) 是 1 到 A 中约数个数的最大值,则可以在 O(nd(A)) 的时间中找到所有的三元组。
询问就是简单的二维偏序,为了平衡复杂度,可以使用 O(1) 修改、O(√n) 查询的分块,总时间复杂度 O(nd(A)+q√n)。
J. Graph Changing
考虑在 G1 中,两点有边当且仅当 |u,v|≥k,如果 u,v 可达,则最短路径长度一定不超过 3(u→1→n→v)。因此如果 k>3,G2 开始就是空图。
当 k=3 时,显然当 n 足够大时 G2 开始也是空图。
当 k=2 时,显然当 n 足够大时 Gi+1 是 Gi 的反图。
当 k=1 时,显然 G1 开始就是完全图。
因此只需要预处理 n 小的情况(例如 n<10),特判 k=1,2,3,剩余的情况分类讨论答案是 1,2,3 即可。
K. Penguins in Refrigerator
先求方案数,考虑从大到小插入数。首先大于 M/2 的数相对顺序不改变,对于不超过 M/2 的每个数 ai,找到左右第一个大于 M−ai 的数,则 ai 只能插入到这个区间中。注意到这些区间形成一棵树形结构,因此方案数就是每个数插入的方案数相乘。
再求字典序最小的方案数。大于 M/2 的数相对顺序不改变,可以连一条链。对于不超过,对于不超过 M/2 的每个数 ai,找到左右第一个大于 M−ai 的数,只需要它们之间的相对顺序不改变即可(因为其他的顺序关系都通过链确定了)。之后用堆维护,求字典序最小的拓扑排序即可。
时间复杂度 O(nlogn)。
L. Prism Palace
所求的就是随机旋转一个角度,有一条边在 y 轴上的投影是整个凸包的概率。对于相邻的两个内角 a,b,这条边满足条件的角度范围是 max{0,π−a−b}。对这些角度求和然后除以 2π 即可。时间复杂度 O(n)。
M. Random Variables
考虑对每个 k 计算每种数出现次数不超过 k 的方案数。其等于 n![xn](k∑i=0xii!)m 注意由于模数不一定是素数,所以不一定有阶乘逆元,但 EGF 的卷积只需要乘上组合数。
考虑容斥,即把 ∑ki=0xii! 写成 ex−∑∞i=k+1xii!。如果能够预处理所有 (∑∞i=kxii!)m,就能够在 O(n2logn) 时间内计算答案(因为 mk≤n)。
这里 m 的范围是 nk,按照 k 从大到小预处理,每次只需给内部的式子加上一项,展开后是 O(m) 项已知的式子求和。因此可以在 O(∑nk=1n3k2)=O(n3) 时间内预处理所有的值。对于每组数据,还要对 0≤i≤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|)。