留 28 张红卡，不升 6931
Lynette_lovely
·
·
生活·游记
考虑逐渐补充 NOI 2025 游记。
Day1
# 社会实践活动
待补。
# Day2
$1.5$ 到 $2$ 小时做出 T1。T2 考虑容斥无法处理逆元。T3 $O(nq \log n)$ 得 $35$ 分。
关于 T2 情况：
> 设
> $$
> 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$ 次数最低次项。
上面“考虑上面过程干了什么事”是考场内容。
事实上大力化简并非自然想法，她要处理的是逆元，而非式子。正如她不能预见到十连能出红而不会浪费 $30$ 彩珀一样，她也不会选择大力推式子。好吧这个逻辑并不正确。总之，从这个角度看，她已经是尽人事了。
以及关于此题与 ULR D 的联系：虽然这题做法确实可能启发 D 题做法，但若提前知道 D 题做法……不知道，可能会知道自己的做法可能做得出来吧。
# 某些已知事件按时间序记流水账
- 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 ？：闭幕式颁奖拍照，然后就出校门了。
# 还有高手
【数据删除】
当试炼场添加了活力值的限制，dot 队、战略队、召唤队、连击队（、回击队、多段队、寒天队、猫猫利簋双通、马蹄金单通、越王利簋、我是千里江山图厨子所以我认为千里江山图在试炼场上可以用【并没有反讽的意味】）逐步统治试炼的队伍，6931 的优势自然逐渐减弱。但这并不是 6931 的问题，只怪逆天策划发现数值膨胀之后用更极端的手段去削减影响。