CF1375H Set Merging
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
Codeforces Luogu CF 上评测 ID 是 #108009000，感觉非常的好看（ 分析 为了方便，设 $a = \frac{1}{m}, b = 1 - \frac{1}{m}$。 枚举第一张是王牌的次数，答案为 预处理斯特林数计算即可。直接递推是 $\mathcal{O}(k ^ 2)$ 的，也可以用 NTT $\mathcal{O}(k \log k)$ 求。 代码 /...
Codeforces Luogu 分析 事实上有 $(a \operatorname{and} b) + (a \operatorname{or} b) = a + b$。那么 于是我们可以求出所有 $a_i$ 的和。这里注意判一下 $\sum b_i + c_i$ 是不是 $2n$ 的倍数。 接着我们就可以求出每个 $a_i$。这里也要注意判一下 $b_i + c_i - \sum a_...
AtCoder Luogu 分析 假设当前要插入一个数 $x$，那么只能插入到序列末尾或者一个 $<x$ 的数之前。 我们把操作序列转化为一棵树，每个节点都是一个二元组 $(w, t)$，表示第 $t$ 次操作在其父节点插入的数前插入了 $w$。为了方便我们新建一个点 $(0, 0)$ 作为根，表示插入到序列末尾。 那么这棵树满足：$t$ 是 $[0, n]$ 的排列、$w\in [0...
AtCoder Luogu 分析 题目相当于限定只能放在两个圆中间，求放 $2n$ 个车的方案数。 事实上我们可以对每一列求出其能放置车的范围 $[L_i, R_i]$。可以发现，对于所有 $i\in[n, 2n)$，都有 $L_i = 0$。 如果所有 $L_i$ 都为 $0$，这就是一个经典问题：将 $R_i$ 从小到大排序，答案即为 $\prod_{i = 0}^{2n - 1} (R...
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1...
Luogu 分析 显然进的球数服从超几何分布，即 $\mathcal{O}(L \log L)$ 预处理一行第二类斯特林数，然后 $\mathcal{O}(SL)$ 计算答案即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==...
UOJ 分析 题目要求的就是 $[l,r]$ 中的数的次大质因子的和，这里的次大是可重集的次大。 首先对其差分，变为求 $[1, n]$ 中的数的次大质因子之和。 这个数据范围启发我们考虑一些筛法，仔细思考之后发现只能考虑 Min_25 筛。 然而直接做显然是不行的。我们需要对其第二部分即求答案的部分进行一些改造，使得它能求出我们想求的东西。 对于一个合数，我们在其剩余的质因子个数 $\le...
LOJ 分析 可以发现答案即为 数论分块计算即可。 再考虑 $\sum \sigma_0\!^2(i)$。我们知道 $\sigma_0\!^2$ 是积性函数，且有 $\sigma_0\!^2(p) = 4$、$\sigma_0\!^2(p ^ k) = (k + 1) ^ 2$，因此可以使用 Min_25 筛计算。 代码 // ===============================...