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。建出 SAM,对于每个 r-l,假设保留所有 \gcd(r,r-l)=1 的 r 对应的结点,这样的串的个数就是这些结点到根的路径的并中深度为 r-l 的点数。如果我们把这些结点按 DFS 序排序,则容易维护这些路径的并。
考虑通过搜索枚举 r-l 包含质因子的集合来优化这个算法。在加入一个素数 p 时,要删除所有 p\mid r 的 r 对应的结点,这样的删除对路径并的变化是删除一条链,可以用链表维护前驱后继,求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案,我们维护每个深度的点数,修改的影响是区间加,查询是单点求值,可以用 O(1) 修改 O(\sqrt n) 查询的分块维护。
接下来只需要分析这样搜索时需要修改的次数 F(n)。实测在 n=10^5 时,修改的次数不超过 2\cdot 10^7。具体的分析是,修改次数等于 \sum_{x=1}^{n-1}[\mu(x)\ne 0]\frac{n}{\mathrm{maxp}(x)},其中 \mathrm{maxp}(x) 是 x 的最大素因子。
时间复杂度 O(F(n)+n\sqrt n)。
D. Bracket Sequence
考虑 DP 计算一个给定字符串 s 的方案数。f(i,j) 表示 S[0:i] 中等于 \mathbb{()}^\infty[0:j] 的子序列的方案数,则答案就是 f(|s|,2k)。
令 K=\max \{k\}。对于第 1 类区间询问,我们可以把这个 DP 写成 v\cdot M_lM_{l+1}\cdots M_r,其中 M_i 是 s_i 的转移矩阵。由于矩阵的特殊性质,可以在 O(K^2) 的时间内计算一个矩阵乘上 M_i,因此只需要预处理 M_1M_2\cdots M_i 和 (M_1M_2\cdots M_i)^{-1},就可以在 O(K) 时间内回答一个询问。
对于第 2 类区间询问,首先可以添加一个 DP 状态,表示还没有进入子串,同时预处理 M_1M_2\cdots M_i 的前缀和即可。
总时间复杂度 O(nK^2+qK)。
E. Dominating Point
令 S(u)=\{v\mid (u,v)\in E\lor u=v\}。点 u 是支配点当且仅当不存在 v\ne u 满足 S(u)\subset S(v)。
把所有点按度数从大到小排序,依次检查是否存在这样的 v。显然我们只需要检查已经确定是支配点的 v,而找到三个支配点后就可以直接返回,因此对于每个 u 只需检查 O(1) 个点,每次检查 O(n)。
总时间复杂度 O(n^2)。
F. An Easy Counting Problem
因为 p 是素数,由 Lucas 定理可知组合数是 p 进制下每一位组合数的乘积。0\le b\le a< p 的组合数分布可以 O(p^2) 暴力计算。
求出一位的组合数分布后,我们要计算其在 i,j\to i\cdot j\bmod p 卷积意义下的 k 次幂。通过找一个原根并将下标取离散对数的变换,我们可以将其转化为普通的循环卷积,可以用 FFT 优化。
时间复杂度 O(p^2+p\log p\log k)。
G. An Easy Math Problem
我们加上 \gcd(p,q)=1 的限制,不同的 (p,q) 就对应了不同的 r。考虑计算这样的 (p,q) 的方案数。显然方案数是积性的,即每个素数独立,且 p^k 的方案数是 2k+1((1,1),(p^i,1),(1,p^i))。分解 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 的倍数满足条件。显然对于固定的 j,i 应该越大越好,k 在满足 k-j\ge j-i 的前提下越小越好。
考虑从大到小枚举 j,找到对应的 i 和 k。i 可以直接找到,但 k 并不单调。然而如果 i 更小的时候 k 更大,这样的三元组一定是不优的,因此仍然是只需要让 k 单调下降。令 A=\max\{a_i\},d(A) 是 1 到 A 中约数个数的最大值,则可以在 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 可达,则最短路径长度一定不超过 3(u\to 1\to n\to v)。因此如果 k>3,G_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|)。