1. CF1728G [*2700]
看到这个 一次合法的照明定义为所有的点都至少被一盏灯照亮，其实我们就应该想到容斥了。
\(m=16\)，那么铁定让我们关于点进行容斥了。容斥有正反两面：强制让选择的点被照到；强制让选择的点不被照到。
前者，我们很难考虑，我们不知道谁会照亮这个点。
但是如果考虑后者：都别靠近我！限制条件会容易一些：对于相邻的两个选中的不能被靠近的点，中间的灯的范围被限制了。把每一个间隔里的灯方案数算出来，乘起来就是这个子集的答案！
预处理数组 \(g[S]\) 表示集合 \(S\) 内的点不被照亮的方案数。没有修改的做完了。
那么单次修改，我们貌似必须去枚举集合 \(S\)？？？这里是一个难点。
我们发现，对于每一个会变权值的子集，真正修改的值只是一个包含这个新灯 \(f_i\) 的区间。我们可以枚举一手这个区间，复杂度 \(\mathcal{O}(m^2)\)。
除了这个区间外，剩下的子集可以乱选。具体怎么修改，我们容易想到 改了这一个间隔 的贡献，也就是说对于一个区间 \([l,r]\)，我们找到 \(\sum \limits_{l,r \in T} g[T]\)，除掉 \((l,r)\) 内部的权值，就是它的贡献，可以 预处理！那么单次修改只需要加上一个 增量 即可。
时间复杂度 \(\mathcal{O}(m2^m + qm^2)\)。
标签：修改,选讲,容斥,计数,子集,区间,照亮,我们 From： https://www.cnblogs.com/BreakPlus/p/17052681.html