Day1

社会实践活动

Day2

设

$$f(S) = \prod_{S \subseteq T} (1 + a_T)$$

$$F(S) = \sum_{S \subseteq T} (-1)^{|T| - |S|} f(T)$$

则 $F(S)$ 表示按位与为 $S$ 的集合的权值之和。

现在要考虑容斥掉两个有交的集合的贡献。枚举集合的交 $S$，它的按位与为 $P$，若两个集合 $T_1, T_2$，按位与 $Q_1, Q_2$，$Q_1 \operatorname{xor} Q_2 \subseteq P$，则 $T_1 \cup S, T_2 \cup S$ 有交且按位与相同。若钦定 $T_1 \cup S, T_2 \cup S$ 的交是 $S$ 的超集，则对于 $S$ 中的每个元素，$T_1$ 和 $T_2$ 都可以选择包含或者不包含，共会造成 $\prod_{i \in S} (1 + a_i)^2$ 的贡献，故设置集合 $S$ 的权值为 $(-1)^|S| \prod_{i \in S} (1 + a_i)^{-2}$。

设

$$g(S) = \prod_{S \subseteq T} \left(1 - (1 + a_T)^{-2}\right)$$

$$G(S) = \sum_{S \subseteq T} (-1)^{|T| - |S|} g(T)$$

则答案为：

$$G(\complement_U S) \sum_S \sum_{U \operatorname{xor} V \subseteq S} F(U) F(V)$$

考虑上面过程干了什么事：

从 $f$ 开始，高维后缀差分，自异或卷积，高维前缀和；从 $g$ 开始，高维后缀差分，翻转（取补集）；两部分点乘贡献到答案。

考虑将前面一部分化简：

$$\begin{aligned} & \sum_{U \operatorname{xor} V \subseteq S} F(U) F(V) \\ =& \sum_{U \operatorname{xor} V \subseteq S} \left(\sum_{U \subseteq T_1} (-1)^{|T_1| - |U|} f(T_1) \right) \left(\sum_{V \subseteq T_2} (-1)^{|T_2| - |V|} f(T_2) \right) \\ =& \sum_{T_1, T_2} (-1)^{|T_1 + T_2|} f(T_1) f(T_2) \sum_{U \subseteq T_1, V \subseteq T_2, U \operatorname{xor} V \subseteq S} (-1)^{|U|+|V|} \end{aligned}$$

对于后面一个和式，发现它等于所有位分别计算和式，再求乘积。打表或者分类讨论得到

$$\sum_{U \subseteq T_1, V \subseteq T_2, U \operatorname{xor} V \subseteq S} (-1)^{|U|+|V|} = [(T_1 \cup T_2) \cap S = \varnothing] 2^{|T_1 \cap T_2|}$$

把交集拆开，所求即

$$\sum_{T_1, T_2} 2^{|T_1| + |T_2| - |T_1 \cup T_2|} (-1)^{|T_1| + |T_2|} [(T_1 \cup T_2) \cap S = \varnothing] f(T_1) f(T_2)$$

设

$$H(S) = \sum_{T_1 \cup T_2 = S} 2^{|T_1| + |T_2| - |T_1 \cup T_2|} (-1)^{|T_1| + |T_2|} f(T_1) f(T_2)$$

用或卷积计算。

$(T_1 \cup T_2) \cap S = \varnothing$ 等价于 $T_1 \cup T_2 \subseteq \complement_U S$，则答案为：

$$\begin{aligned} & \sum_S \left(\sum_{S \subseteq T} > (-1)^{|T| - |S|} g(T)\right) \left(\sum_{T \subseteq S} H(T) \right) \\ =& \sum_S g(S) H(S) \end{aligned}$$

最后考虑处理 $a_i \equiv -1$ 的特殊情况。最暴力的方法是将 $\sum_{S \subseteq T} [a_T \equiv -1]$ 相同的 $S$ 单独做，并将这样的 $a_i + 1$ 在计算 $f, g$ 的过程中视为 $1$。但发现只要在做或卷积时，令 $\sum_{S \subseteq T} [a_T \equiv -1]$ 不同的 $S$ 在计算时互不干扰，也可以达到单独做的效果。另一种理解方式是令 $x = -1 + 1$，并维护 $x$ 的多项式，由于负数次幂的 $x$ 不会贡献到答案上，所以只需维护 $x$ 次数最低次项。

某些已知事件按时间序记流水账

• 7.16 13:30：好好吃饭。
• 7.16 14:00：看物华 PV。应当几乎看过所有器者 PV。记得的有海水江崖炉、狸猫盘、百花图卷、铜壶滴漏、雪景寒林图以及银香囊角色预告。
• 7.16 14:30~？：疑似在睡觉。也可能在刷视频。
• 7.16 ？：好好吃饭。
• 7.16 ？：谈话。后继续刷视频。
• 7.16 ？：篝火晚会。无特殊记录。
• 7.16 ？：物华直播，看号，调整武器及深造后，问 $32$ 红卡二致酒帐零致素纱襌衣，答曰知所思切勿，论宋真珠舍利宝幢，可待银雀山《孙子兵法》《孙膑兵法》汉简池。
• 7.17 ？：好好睡觉。
• 7.17 7:00：谈话。
• 7.17 9:30：参加活动。
• 7.17 10:00：双子池开，共投入 $150$ 抽，连歪 $3$ 发，甚至有超 $60$ 抽出货但歪。已无可用资源。未使用彩珀兑换请调券。疑彩珀不足。亦疑此时并没有十发出红并且拿真珠宝幢想法，苦尽甘未必来。
• 7.17 11:30：活动结束后唱红歌。后回寝室唱惊鹊。好好吃饭。
• 7.17 ？：闭幕式颁奖拍照，然后就出校门了。

还有高手