• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AtCoder ABC 215 简要题解

admin

11月 28, 2021

A – B

模拟

C

可以直接爆搜,也可以写逐位确定的多项式复杂度算法,使用多重组合式求随意乱排的方案数。

D

首先对 (A) 所有数暴力分解质因数,然后把遇到过的质因数打上标记。

接下来再对 (1 sim m) 暴力枚举然后分解质因数 (m check) 即可,复杂度 (mathcal{O}((n + m) sqrt{W}))

E

看错题耽误了半小时。。。直接状压:令 (f_{i, j, S}) 表示当前考虑到第 (i) 位上一个选出来的比赛为 (j),当前已经选出的比赛二进制压位后为 (S) 的方案数。

转移显然,复杂度 (mathcal{O}(10n2 ^ {10}))

F

二分答案,问题转变为是否存在一对点对 (x, y) 坐标之差均 (ge mid)

首先将所有点按照 (x) 坐标排序,考虑 ((i, j)(i < j)) 这个点对是否合法在 (j) 处统计。

那么对于 (j) 可行的 (i) 是一段前缀,我们维护这段前缀 (y) 的最大最小值即可判断。

注意到随 (j) 递增可行的前缀不减,于是可以双指针扫过来,复杂度 (mathcal{O}(n (log W + log n)))

G

根据期望的线性性,我们考虑每种颜色对答案的贡献。

可以发现贡献只与颜色出现次数有关,注意到本质不同的出现次数只有 (sqrt{n}) 个,于是我们把出现次数相同的颜色一起计算贡献,复杂度 (mathcal{O}(n sqrt{n}))


貌似题解还有 (mathcal{O}(n mathrm{Poly}(log n))) 的做法,不会 (m PGF) 先鸽。。。

H

首先考虑什么情况是合法的。

容易扩展 (m Hall) 定律得到局面合法当且仅当:(forall S in V_b, sumlimits_{i in S} b_i le |igcuplimits_{i in S, c_{j, i} = 1} a_j|)(写的不是很严谨,右侧是所对应集合 (a) 的和)。

由于 (m) 很大 (n) 很小,因此我们考虑枚举右边的集合 (T),那么就要求出左边有那些集合 (S) 出边构成的并集恰为 (T),设为 (P_T),那么不难得到第一问答案为:

[minlimits_{T, p_T
e varnothing} sumlimits_{i in T} a_i – left(maxlimits_{S in P_T} sumlimits_{j in S} b_jight) + 1
]

不难观察得:取到最大值的集合 (S in P_T) 一定是 (P_T) 内所有集合的并,因此就不需要枚举所有集合 (S in P_T) 了,只需要求出所有 (P_T) 内集合的并 (P_T’) 即可,那么可将答案改写为:

[minlimits_{T, P’_T
e varnothing} sumlimits_{i in T} a_i – sumlimits_{j in P’_T} b_j + 1
]

同时继续观察可以发现:我们可以放宽条件使得答案依然不变(令 (s_j)(j) 这个公司可以接受的菜品压位构成的二进制数):

[minlimits_{T, exist i, s_i subseteq T} sumlimits_{i in T} a_i – sumlimits_{s_j subseteq T} b_j + 1
]

于是我们只需 (forall S, mathrm{count} : f_S = sumlimits_{i = 1} ^ m [s_i subseteq S] b_i) 即可计算得出第一问的答案。

那么我们直接令 (g_{S} = sumlimits_{i = 1} ^ m [s_i = S] b_i),这个可以 (mathcal{O}(m)) 简单得到,然后做一边子集和(高维前缀和)即可,复杂度 (mathcal{O}(n2 ^ n))

接下来考虑第二问,根据第一问可以得知,问题显然可以转化为:

  • (n) 种物品,第 (i) 种物品有 (a_i) 个,所有物品之间(包括同种物品)有标号,接下来需要从中取出 (m) 个元素,接下来给出 (k) 个集合,要求选取出的所有元素至少完整地被一个集合包含,求方案数。

考虑容斥,计算得到不合法的方案数。

首先不难得到一个朴素的 (m dp) 方法,令 (f_{i, j}) 表示考虑完前 (i) 个集合,当前集合的交集为 (j) 的容斥系数之和。

转移显然,复杂度 (mathcal{O}(4 ^ n)),不能接受。

可以发现,问题在于如何快速地得到选出若干个集合并集恰好为 (S) 的容斥系数之和。

对此,我们考虑使用 另一个容斥来求出此容斥系数之和

具体地,我们令 (g_S) 为钦定选出若干个集合并集至少为 (S) 的方案,那么有(令给出的集合为 (T_{1, 2, cdots k})):

[g_{S} = [
exists i, S subseteq T_i]
]

为了求 (g),我们考虑直接计算得到:

[g’_S = sumlimits_{i = 1} ^ k [S in T_i]
]

然后得到 (g) 的方法显然,对于此我们做一边超集和(高维后缀和),复杂度 (mathcal{O}(n2 ^ n))

那么就满足二项式反演的集合形式,令 (f) 为恰好的方案,根据二项式反演易得:

[f_S = sumlimits_{S subseteq T} (-1) ^ {|T| – |S|} g_T
]

容易发现这是一个异或卷积的形式,直接做 (m FWT) 即可,复杂度 (mathcal{O}(n2 ^ n))

当然你也可以不写 (m FWT),我们将 ((-1) ^ {|S|}) 提出最后乘上去,那么后者也是一个超集和,可以直接计算。

那么最终第二问的答案为:

[Ans2 = dbinom{sumlimits a_i}{ans1} – sumlimits_S f_S imes dbinom{sumlimits_{i in S} a_i}{ans1}
]

总体复杂度 (mathcal{O}(nm + n2 ^ n))

GO!

发表回复

您的电子邮箱地址不会被公开。