KeBlog

概念

一个有向图 \(G = (V, E)\) 的闭合子图是一个导出子图 \(G_0 = (V_0, E_0)\) ，满足 \(\forall u \in V_0, (u, x) \in E\) 有 \(x \in V_0\) 成立。

最大权闭合子图即点权和最大的闭合子图。

去年写过的东西加点补充就算做今天写的了

基本概念

首先得知道链和反链是什么。

在 有向无环图（ DAG ） 中，
链是满足任意两点 x, y 要么 x 可以到达 y 要么 y 可以到达 x 的点集 （即使只有一个点），
反链是任意两点没有路径的 点集 。

那么最长反链，就是点的个数最多的反链。

给定一张图，求边权和最小的简单环的大小。

无向图或者有向图都可以做，需要注意的是无向图直接转成有向图会得到不合法的重边二元环。

以下讨论用 \(n, m\) 分别表示图的点数和边数，为了方便，只讨论简单无向图，其他情况不难扩展。

并且只考虑边权非负的情况。

标题就取 HNOI2020 吧，最后是游记还是退役记，也难说。

本来是对 5 月初省选做准备的，结果省选时间因为疫情一推再推。5 月初的一个星期参加了正睿的线上集训，考了几次，状态 不错，甚至有些超常，这段时间左右大概是状态最佳的一段时期，或许这时候省选我能占优势吧。

可惜后来慢慢地状态在下跌，直到省选时间终于敲定，就只剩两个星期了，争取能把状态提起来吧。

关于省选这回事，过去两年没有什么压力，进了就进了，没进就没进，可是到了高二感觉完全不同，毕竟是关乎到退役以及参 加最后一次（对我而言也是唯一一次） NOI 的机会的。因此最近总是会突然感到紧张，心跳莫名的加速，甚至控制情绪都变得 困难起来。这大概是什么焦虑症吧，不过也无所谓，毕竟能这样焦虑的机会也不多。

我参考了很多数据，也有认真思考过今年有多大把握进入省队。听说北京省选取消了，直接按 CSP 成绩划分，然后我也认真看 了看湖南去年的 CSP ，发现自己排在二十名开外（不过倒是有北京队线），因此这次省选我是不占优势的，起手就比别人低， 想要进队，还是需要不少的进步的。很迷茫，我并不知道这半年来的进步到底够不够，我很希望能用自己的实力赢得我想要的， 而不是靠运气，虽然运气的确是一个很重要的因素，但我不喜欢自己的命运完全被运气这种虚无缥缈的东西左右。

说起运气，我似乎也曾被运气眷顾过，那是初三的 NOIP ，我学了几个月就意外地拿到了提高一等奖，这是完全出乎意料的，也 正是这个一等奖，直接促使我选择了坚持走 OI 这条路。至于后来的重要的几次考试，主要是有各种失误，那都是后话了。

另外，学 OI 学得越久，见识到越多，就越发地认识到自己能力的不足，有些人实在就是强的离谱，实力超乎想象，那些我都不 曾敢去想象的高度就是能被他们轻松达到。这是客观事实，也许只能坦然接受，好在我并不必要去和他们相争，我没有那么大的 野心，但却也有自己的目标和想法，如果能实现自己的梦想，便也能心满意足了，尽管在部分人看来可能微不足道。

以上，考前焦虑的 Kewth 在省选前的一些乱七八糟的杂想。

nameplate

syzoj 的数据库的 user 表有 nameplate 这个属性，代码里面也有关于 nameplate 的处理， 但是不知道为啥前端并没有给出任何关于 nameplate 的接口，自己写个前端接口就好了。

比如在 views/user_edit.ejs 里面添加关于 nameplate 的修改，然后在 modules/user.js 实现具体的修改即可。

当然不希望在前段开放接口的话也可以直接在数据库里操作。

以下简称超现实数 Surreal Numbers 为 SN 。

超现实数完整的理论很复杂，这里不详细给出。

对于两个集合幂级数 \(f\) 和 \(g\) ，定义其和 \(h\) ：

\[ h_S = f_S + g_S \]

对于两个集合幂级数 \(f\) 和 \(g\) ，定义其乘积 \(h\) ：

\[ h_S = \sum_{T \subseteq S} f_T \times g_{S \setminus T} \]

即常说的子集卷积。

异或卷积的本质就是 \(n\) 维循环卷积。

二维卷积

可以理解为对于二维数组 \(f\) 和二维数组 \(g\) 求二维数组 \(h\) ：

\[h_{i,j} = \sum_{a+b=i} \sum_{c+d=j} f_{a,c} \times g_{b,d}\]

这个 \(h\) 就是 \(f\) 和 \(g\) 的二维卷积。

构造生成函数数组 \({F_i}, {G_i}, {H_i}\) ，满足 \(F_i = \sum_{j} f_{i,j} x^j\) ，类似地定义 \({G_i}\) 和 \({H_i}\) ，那么有：

\[H_i = \sum_{a+b=i} F_a \times G_b\]

简单来说就是快速计算 \(\binom{n}{m} \bmod p\) 。

卢卡斯定理

如果 \(p\) 是质数，有 \(\binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \binom{n/p}{m/p} \pmod{p}\) ，其中 \(n/p\) 和 \(m/p\) 表示整除。

直接递归调用，预处理阶乘，单次询问时间复杂度 \(O(p + \frac{\log n}{\log p})\) 。

问题是这样的：

对于一个无穷大的递推数列 \(\{h_i\}\) 和长度为 \(k\) 的已知数列 \(\{a_i\}\)，满足\(\forall n, h_n = \sum_{i=1}^k a_i h_{n-i}\) 。 已知 \(h_i (0 \le i < k)\) 求 \(h_n\) 。

直接递推复杂度 \(O(nk)\) ，矩阵快速幂可以做到 \(O(k^3 logn)\) 的复杂度，这里介绍一个更优秀的做法。

结论

便于以后复习，先给出结论。

1. 构造多项式 \(F(x) = x^k - \sum_{i=1}^k a_i x^{k-i}\) 。
2. 求出多项式 \(G(x) = \sum_{i=0}^{k-1} c_i x^i = x^n \bmod F(x)\) 。
3. 有 \(h_n = \sum_{i=0}^{k-1} c_i h_i\) 。

第一步和第三步都是 \(O(k)\) 的，而第二步通过多项式快速幂和多项式取模可以做到 \(O(k\log k\log n)\) 的复杂度。

当然暴力做多项式快速幂和多项式取模也能做到 \(O(k^2 \log n)\) 的复杂度，大多时候这就足够了。