PDF《NOIP2018 模拟赛 T2 题解 update》

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOIP2018 模拟赛 T2 题解 update 租酥雨

2018 年10 月18 日 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 出题前就觉得 T2 的标算很假考场上大概率被踩标算. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 出题前就觉得 T2 的标算很假考场上大概率被踩标算. 今天上午我跑到小机房找叶佬和菊开讨论 T2 有没有更优做法. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 出题前就觉得 T2 的标算很假考场上大概率被踩标算. 今天上午我跑到小机房找叶佬和菊开讨论 T2 有没有更优做法. 然后他们想了半天告诉我没有. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 出题前就觉得 T2 的标算很假考场上大概率被踩标算. 今天上午我跑到小机房找叶佬和菊开讨论 T2 有没有更优做法. 然后他们想了半天告诉我没有. 然后今天下午... 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 问题可以被转化为:一共有 d(L) 个数,每个数都是一个 2k 位的 二进制数,求有多少种方案使得选出的所有数或起来为全集. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 问题可以被转化为:一共有 d(L) 个数,每个数都是一个 2k 位的 二进制数,求有多少种方案使得选出的所有数或起来为全集. 令f(s) 表示选出一些数或起来值为 s 的方案数.f(s) 不好求,考 虑求 g(s) = ∑ i?s f(i). 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 问题可以被转化为:一共有 d(L) 个数,每个数都是一个 2k 位的 二进制数,求有多少种方案使得选出的所有数或起来为全集. 令f(s) 表示选出一些数或起来值为 s 的方案数.f(s) 不好求,考 虑求 g(s) = ∑ i?s f(i). 而这个 g(s) 怎么求?假设一共有 cnts 个数是 s 的子集,那么 g(s) 就是 2cnts . 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 既然已经求出了 g(s),那么 f(s) 随便容斥一下就好了.容斥系数 为±1. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 既然已经求出了 g(s),那么 f(s) 随便容斥一下就好了.容斥系数 为±1. 如果强制要求选某个数 ai,那就可以只考虑所有 ai 在二进制下 为0的二进制位,相当于是缩小了原题的数据规模后的一个子问 题. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 既然已经求出了 g(s),那么 f(s) 随便容斥一下就好了.容斥系数 为±1. 如果强制要求选某个数 ai,那就可以只考虑所有 ai 在二进制下 为0的二进制位,相当于是缩小了原题的数据规模后的一个子问 题. 算法复杂度 O((d(L) + 2k) * 22k), 比辣鸡出题人的标算高明到不 知道哪里去了. 租酥雨 NOIP2018 模拟赛 T2 题解 update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 祝大家 NOIP2018 rp++! 租酥雨 NOIP2018 模拟赛 T2 题解 update