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),那么不难得到第一问答案为:
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’) 即可,那么可将答案改写为:
e varnothing} sumlimits_{i in T} a_i – sumlimits_{j in P’_T} b_j + 1
]
同时继续观察可以发现:我们可以放宽条件使得答案依然不变(令 (s_j) 为 (j) 这个公司可以接受的菜品压位构成的二进制数):
]
于是我们只需 (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})):
exists i, S subseteq T_i]
]
为了求 (g),我们考虑直接计算得到:
]
然后得到 (g) 的方法显然,对于此我们做一边超集和(高维后缀和),复杂度 (mathcal{O}(n2 ^ n))。
那么就满足二项式反演的集合形式,令 (f) 为恰好的方案,根据二项式反演易得:
]
容易发现这是一个异或卷积的形式,直接做 (m FWT) 即可,复杂度 (mathcal{O}(n2 ^ n))。
当然你也可以不写 (m FWT),我们将 ((-1) ^ {|S|}) 提出最后乘上去,那么后者也是一个超集和,可以直接计算。
那么最终第二问的答案为:
]
总体复杂度 (mathcal{O}(nm + n2 ^ n))。