打算要写的东西

打算要做的事

NcatBot 是一个用于 QQ-Bot 开发的 Python SDK.

0301测试

考试

T1

考虑如何检查一个条件是否合法，如果最高位为任意，那么两边需要都合法，否则要求两边至少有一个合法。

考虑两边的检查，发现第 \(i\) 层的节点个数为 \(2^i\)，总的情况数为 \(2^{n-i}\)，因此可以记忆化搜索一下。用一个 \(mask\) 的前若干位表示限制，后若干位表示高位的数字即可。

也可以这样想：考虑算所有的情况，设 \(T(n)\) 表示计算第 \(n\) 层所有情况的复杂度，暴力计算有 \(T(n)=2^n+4T(n-1)=2^{2n}\)，实际上发现对于只有第 \(n\) 层不同的情况可以只算一次，于是 \(T(n)=2^n+2T(n-1)\)，得到 \(T(n)=n2^n\)。

T2

做法一

考虑钦定 \(A\) 组先选满，枚举 \(A\) 组选满的位置计算对应概率然后再乘二。对于每一个位置 \(p\)，基本情况总数为 \(\binom{p-1}{n-1}\)，每种基本情况等概率取到，概率为 \(2^{-p}\)，分三类讨论

• 如果 \(x_k<p\)，那么 \(k\) 个人既可以在 \(A\) 组也可以在 \(B\) 组，对应的基本情况数分别为 \(\binom{p-1-k}{n-1-k}+\binom{p-1-k}{n-1}\)。

• 如果 \(x_k=p\)，那么一共有 \(\binom{p-k}{n-k}\) 种基本情况。

• 如果 \(x_k>p\)，首先 \(p\notin X\)，然后记 \(c\) 为 \(p\) 之前的 \(x\) 个数，基本情况总数为 \(\binom{p-1-c}{n-1}\)。

于是有一个 \(nq\) 的做法。

观察到查询的答案是一个二元函数 \(f(p,x)\) ，对于 \(x\) 较小的情况可以预处理前缀和，对于 \(x\) 较大的情况，查询数比较少，可以暴力。于是有一个 \(n\sqrt q\) 的做法。

进一步观察，\(2^{-p}\binom{p-1-c}{n-1}\) 可以很容易的预处理 \(2^{-p}\binom{p-1}{n-1}\) 的前缀和然后查询时乘上一个 \(2^{-c}\)。

对于 \(2^{-p}\binom{p-1-k}{n-1-k}\)，答案应该是： \[ \begin{align} \sum_{p=x_k+1}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}&=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}\\ &=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-p}\\ &=\sum_{p=\max(n,x_k+1)-k-1}^{2n-1-k-1}2^{-p-k-1}\binom{p}{n-k-1}\\ \end{align} \] 注意到 \(\sum k\) 其实很小。

好吧，我不会线性做法，摆了。

做法二

先只算都在 \(A\) 组的情况，然后分 \(B\) 选满的位置 \(p\) 所在的区间讨论。

• \(p>x_k\)：令 \(x_k\) 及之前每一种可能的硬币选择为基本情况，需要计算在 \(x_k\) 处 \(X\) 都取到 \(A\) 且 \(B\) 不能被选满的方案总数，隐含条件是 \(x_k\) 之前 \(A\) 也不能被选满。

  可以暴力的算组合数，枚举剩下的 \(x_k-k\) 个数有多少个分配到 \(A\) 中，可以直接限制 \(A,B\) 都满足要求，即 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n-k}\binom{x_k-k}{i}\)。

  然后 \(\sum k\) 是比较小的，于是放宽一下限制，算 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n}\binom{x_k-k}{i}\) 再减掉，容易发现这个式子只和 \(x_k-k\) 有关，而这个式子本身也不是很难算，进一步的将 \(\max\) 的限制去掉，变成 \(\sum\limits_{i=0}^n \binom{x}{i}\)，然后对于 \(x-n\ge0\) 的情况，需要减去 \(\sum\limits_{i=0}^{x-n}\binom{x}{i}\)。都可以拆组合数然后动态规划。 \[ \begin{align} \sum\limits_{i=0}^{x-n}\binom{x}{i}&=\binom{x-1}{0}+\sum\limits_{i=1}^{x-n}\binom{x-1}{i-1}+\binom{x-1}{i}\\ &=\binom{x-1}{0}+\sum_{i=1}^{x-n}\binom{x-1}{i}+\sum_{i=1}^{x-n}\binom{x-1}{i-1}\\ &=\binom{x-1}{x-n}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}\\ &=\binom{x-1}{x-n}+2\sum_{i=0}^{x-1-n}\binom{x-1}{i} \end{align} \]

  另一种考虑方式是算一个 \(f_w\) 表示一共 \(w\) 个，\(A,B\) 都不超过的情况总数，然后需要减去 \(B\) 抵到的情况数，然后又因为需要把 \(A\) 超过的情况去掉，\(A\) 超过是因为 \(k\) 个被塞进了 \(A\)，分别枚举超过 \(1,2,3\cdots k\) 个减掉对应的基本情况数即可。\(f_w\) 的转移考虑直接放 \(A,B\) 然后去掉不合法的情况。

• \(x_{i-1}<p<x_{i},i\in[1,k]\)

  将基本情况定为 \(x_i\) 之前（不含）的硬币状态，限制有两个，\(|B|\) 不小于 \(n\)，且 \(X\) 内的是必须为 \(A\) 的。满足 \(A\) 限制的总情况数为 \(2^{x_i-i}\)。满足 \(A\) 限制但不满足 \(B\) 限制的情况数为 \(\sum\limits_{i=0}^{n-1}\binom{x_i-i}{i}\)，先扣掉。这里不需要考虑 \(A\) 被选满，因为 \(A\) 被选满的情况确实应该扣掉。然后再减去再 \(x_{i-1}\) 之前就满足 \(B\) 限制的所有情况，注意额外带一个 \(2_{x_i-x_{i-1}-1}\) 的系数。

  这里还会有一些误解，其实隐含了 \(|A|<n\) 的限制，实际上如果这两个限制都满足那么这个隐含限制一定满足，因此不管这个隐含限制直接算也是可以的。

当使用容斥计算 "恰好" 时，应该减掉上一次的 "至少" 而不是 "恰好"，记录 \(lst\) 的时候要注意。

T3

先考虑构造一种合法的解满足条件。挨个确定值的办法并不好弄。考虑先确定前 \(i\) 个的大小关系，如果前 \(i\) 个合法了，并且第 \(i+1\) 个可以放到一个位置，满足前面没有不小于 \(a_{i+1}\) 且存在至少一个 \(a_{i+1}-1\)，那么就合法。于是得到一个有解的充要条件：任何一个前缀 \(a_i\) 值的集合连续。

现在考虑算 \(i\) 位置的答案，它前面的不小于它的元素必须在它后面，它后面的元素可以线性扫一遍，维护前缀连续最大值算出来。

考虑优化，对于一个 \(i\) 算答案的时候，就是要找到依赖它以及它前面不小于它的元素的所有元素。后面的比 \(a_i\) 大的元素如果能在 \(i\) 之后找到一个 \(a_i\) 依赖，那么就可以被放在 \(i\) 前面。

元素的依赖关系好像是构成一棵树的，于是建树，每个元素向它的第一个前驱连边，然后 \(i\) 节点以及它同层左边的兄弟里所有节点都不能放在 \(i\) 前面，于是算出了 \(p_i\) 的最大值。

0228测试

考试

T1

毒瘤计算几何。

考虑一步的过程，是从一个点的一个方向开始旋转，于是对所有目标点极角排序，极角相同的长度较长的放前面，查询就是要找到接下来的第一个长度小于当前长度的。

一个很暴力的想法是直接开始跳，如果遇到了相同的点说明有环，然后模环长再跳，这样每个点期望经过 \(O(\log)\) 次，总共要处理 \(O(nm\log n)\) 次，感觉很可做。

接下来的问题变成了如何快速查询。考场上觉得排序后确实是查第一个比它大的，但是要带上删除，于是考虑长度倒序做。然后想 set 暴力操作肯定要超时，然后考虑用并查集做删除操作，用优先队列维护长度的处理顺序。

很麻烦，写不出来。

实际上可以不带删，考虑找到第一个极角超过查询极角的位置，在上面二分第一个长度满足限制的，用 ST 表做长度查询，复杂度 \(O(\log n)\)。

找环的时候需要注意不是点重复而是边重复才出现环，判断需要再检查一下来向，需要记录当前点上一次访问时有几个点，走了多远，从哪个来的。

总复杂度 \(O(Tnm\log^2n)\)。因为卡不满所以能过。

带删的查询问题都很麻烦，考察之前先想想能不能不删。

T2

首先考察 \(1\) 是不是重心，如果 \(1\) 不是重心那么一定会向重心移动？不对，可以先往重心走一步，让重心的点相互消耗，然后往回去。

考虑目标点和 \(1\) 之间的毛毛虫。毛毛虫任意两个端点都是可以相互抵消大小的。因此如果毛毛虫所有端点大小和为偶数且没有任何一个端点大小超过 \(\frac{totalsize}{2}\)，那么一定可以移动到目标点。

如果有一个大小超了，考虑能不能在它的内部抵消，是可以的，考虑计算一下某棵子树最少要将中心往自己的方向拉几步，同时也不难证明最少步数到 \(sz\) 之间每一个奇偶性相同的步数都能取到。

最小步数是可以动态规划的，转移看是否有一个儿子的 DP 值超过其它儿子的大小总和，还要看当前子树大小奇偶性。可以拿个类记录一下 DP 值最大的儿子和对应的子树大小以及总的子树大小。因为如果有儿子 DP 值超过其它儿子总大小，那么这个儿子的 DP 值一定是最大的，所以这样没问题。

然后考虑计算答案，直接再 DFS 一遍，判断合法性的信息就是转移的那个信息，很容易合并的，额外算一个后缀和就行。

T3

最开始想能不能把限制弄成不包含或者不交，然后发现不行，由于 \(x_i\) 可能相等，所以不交也是不现实的。然后想能不能从位置入手做，比如区间 DP 或者扫描 DP，还是不好处理。

就算是容斥，同样不好考虑位置。

考虑从值本身入手做，每段位置有一个限制，然后考虑一个限制，可能让它满足条件的段是一段区间，而且使值不同的限制满足的位置集合不交。说人话就是不同值的限制独立，一段上界相同的位置只会满足值是其上界的限制。因此可以上界不同的段分开做然后乘起来。

将区间弄成左闭右开方便处理，然后离散化暴力算每一段的上界，上界记在左端点。枚举每个值，暴力将每一段放进去，然后将对应的限制挂在新标号的位置上去。

然后设 \(dp[i][j]\) 表示考虑到前 \(i\) 个，上一个抵到上界的位置是 \(j\) 的方案数，在右端点还需要将不满足挂上的限制的状态清掉。

复杂度 \(O(q^2T)\)。

其实有 \(O(Tq\log q)\) 的做法，暴力算上界可以用单点改后缀查的树状数组优化，暴力放段的过程可以用 vector 记一下每一个值具体有哪些段和哪些限制。

动态规划中，先对限制的左端点取前缀 \(\max\)，然后可以考虑枚举最后一个 \(1\) 的位置转移，然后转移可以双指针加标记搞定。

多项式算法

多项式是组合计数题目中非常重要的工具。

约定

幂级数用大写字母表示，系数用对应的小写字母表示，对于 \(F(x)\)，\(f_i\) 就是 \(F(x)[x^i]\)。

多项式乘法

应用

对于形如 \(f_k=w(k)\sum\limits_{i+j=k}a_ib_j\) 的 \(f_k\)，可以利用多项式乘法在 \(O(n\log n)\) 的时间里解决。

或者说，对于形如 \(F(x)=A(x)\cdot(B(x) * C(x))\) 的幂级数 \(F(x)\) ，可以在 \(O(n\log n)\) 的时间里求出。

多项式求乘法逆

一般被描述对于一个 \(F(x)\) 找一个 \(H(x)\)，满足 \(F(x) * G(x)\equiv 1\pmod{x^n}\)。

可以用定义法配合分治 FFT 在 \(O(n\log^2 n)\) 的时间内解决： \[ h_n=\dfrac{-\sum\limits_{i\in[0,n)}f_ih_{n-i}x^n}{f_nx^n} \]

第二种方式是倍增法，假设我们已经求出了 \(H'(x)\) 满足 \(H'(x) * F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}\)。又显然有 \(H(x) * F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}\)。两式相减得 \((H'(x) - H(x)) * F(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}\)。平方得 \((H'(x) - H(x))^2 * F^2(x)\equiv 0\pmod{x^n}\)。 \[ \begin{align} (H'(x) - H(x))^2 * F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F^2(x)-2H'(x)H(x)F^2(x)+H^2(x)F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F(x)-2H'(x)+H(x)&\equiv 0\pmod{x^n}\\ H(x)&\equiv -2H'(x) - H'^2(x)F(x)\pmod{x^n}\\ \end{align} \] 其中第二行到第三行先同时除以 \(F(x)\) 再对 \(F(x)\) 和 \(H(x)\) 进行乘法得到 \(1\)。

对于 \(n=1\) 我们显然有 \(H'(x)=f_0^{-1}\)，然后依次推出即可。

0217测试

考试

T1

非公平组合游戏，先考虑简单的情况，不妨设 \(x_i\le a+b,a\le b\)。

那么一个 \(x_i\) 要么能被两个人各自拿一次，要么只能被 \(A\) 拿。

如果存在一个只能被 \(A\) 拿的 \(x\)，那么 \(A\) 必胜，他只需要一直拿两人都能拿的 \(x_i\)，让 \(B\) 拿不了，由于 \(A\) 最后多一个，所以必胜。

如果不存在只能被 \(A\) 拿的 \(x\)，胜负就与 \(x\) 的奇偶性和谁先手有关。但是此时两个人并不是等价的。如果有一个 \(x\) 满足 \(\max(2a,b)\le x\)，那么 \(A\) 只要拿掉它就能创造一个只能被 \(A\) 拿的，又变成必胜了，所以 \(B\) 会优先拿掉它们，但是如果由两个，\(B\) 就没办法。

分谁先手后手讨论，容易给出四种情况的充要条件，这些充要条件也是便于直接构造计算的。

考虑迁移到 \(x_i\) 无限制的情况，发现状态不会改变，如果先手必胜，那么先手按照模意义下的最优策略走，如果后手选择了能取模的，那么先手也选它取模，直到后手选择了一个不能取模的，此时可以平行对应到取模的情况，然后先手继续按照模意义下策略走。

后手必胜同理。

将整个转移图画出来，取模的情况就是完整转移图的低维投影。如果走了投影上没有的边，另一个人一定可以将点搬回投影上。

教训

犯错的原因是考虑简单情况时理所当然的认为 \(b\le y_i\) 时，该堆石子对 \(A,B\) 等价，实际上这不是等价的。

罗列证据时考虑要全面，或者干脆对拍一下。

T2

又没读题，最开始当成正回文做，手玩下样例保证理解对题。

在确定前半段的过程中，后半段也随之确定，建目标串的反串，对应点表示前半段出现什么时可以到该状态。然后跑 AC 自动机上动态规划，合并的时候由于一个串一定是由正串的一个前缀和反串的一个前缀拼起来的，如果可以拼起来那么当前 AC 自动机的节点一定满足它能代表其中较长那个前缀，直接暴力检查。

教训

• 手玩样例保证读对题。
• AC 自动机的点权值要弄对（除了 fa 之外还有 fail 的权值）。
• 要对拍。

T3

最开始考虑直接对树进行动态规划，设 \(dp[j][i]\) 表示有 \(i\) 个叶子，最大左儿子深度为 \(j\) 的方案总数。答案是一个前缀和，转移枚举左右儿子大小，也是前缀和形式，看上去不好优化。于是直接对前缀和动态规划，然后推出一个连分数形式的生成函数，不会了。

其实二叉树可以考虑转成序列做，由于一颗 \(n\) 个叶节点的满二叉树唯一对应一个 \(n-1\) 对括号的括号序列，要求等价于求 \(n-1\) 对括号，最深不超过 \(m-2\) 的括号序列个数。

可以抽象到二维平面上做，需要走到 \((n-1,n-1)\)，不能碰到 \(y=x+1\) 和 \(y=x-m+1\)。简记一条直线为它的截距，即 \(1\) 和 \(-m+1\)。

两种错误的方式

• 考虑先算碰到 \(1\) 的方案数，然后再算碰到了 \(-m + 1\) 但没碰到 \(1\) 的方案数。前者好算，后者对称后不能碰到 \(1\) 且不能碰到 \(1\) 关于 \(-m+1\) 的对称直线 \(-2m+1\)，递归解决该问题，边界为限制彻底放开。
• 考虑算碰到了 \(1\) 或者碰到 \(-m+1\) 的方案数，加上同时碰到的方案数，对于同时碰到的方案数，不容易一起算，考虑算先碰到 \(1\) 再碰到 \(-m+1\) 的方案数，同样考虑对称，先关于 \(1\) 再关于 \(-m+1\) 对称。同时要求走到 \(1\) 的过程中不能碰到 \(-2m+1\)，即减掉先碰到 \(-2m+1\) 关于 \(1\) 再碰到 \(1\) 的方案，递归解决。

容斥方式的本质

容斥本质上是通过对称构造了一个没有限制的问题，使得它和原问题不满足限制的情况一一对应。

这个对应的证明是基于对称问题中起点到终点一定穿过直线，因此将第一次碰到直线的前部分对称后一定可以对应到一种原问题的不合法情况，所以考虑原路径时，在对称路径第一次穿过直线后，原路径就不再是对称路径的对称路径了。所以第一种方式对直线 \(-2m+1\) 的限制是不合理的。

方式二看上去修了锅，实际上只是展开了一层手动修了，后面还是有一样的问题。

如果目标点在直线异侧，那么因为答案不是良定义的所以会错，需要特判为 \(0\)。

关于容斥方式，如果将括号序列视作一个 +1 -1 的序列，那么合法就是要求前缀和最小值不小于 \(0\)，我们将第一个小于 \(0\) 后的翻转，最后一定会到达 \(-2\)，因此不合法方案数等于到 \(-2\) 的无限制方案数。

一种正确的方式

全部方式减去要求碰到 \(1\) 或者 \(-m+1\) 的方式，发现先碰到 \(1\) 再碰到 \(-m+1\) 的方式被算重了。

然后要算先碰到 \(1\) 再碰到 \(-m+1\) 的方式，算这个的时候发现先到 \(-m+1\) 再到 \(1\) 再到 \(-m+1\) 的方式又被算重了，需要减去，如此递归下去做。

bonus

• 构造满二叉树的方式：

  • 单个叶子节点是空串
  • 有儿子的节点记左右儿子为 \(A,B\)，令它为 (A)B。
  • 容易证明它们是一一对应的。

• 构造二叉树的方式：

  • 空树是空串。

  • 单节点的树是 ()。

  • 有儿子节点的树记左右儿子的构造分别为 \(A,B\)，令它为 (A)B。

  • 容易证明方案是一一对应的。

0215测试

考试

T1

期望题的统计方式有很多，主要有以下几种：

1. 枚举可能的最终状态，计算其概率和权值并加和。

   • 对于每种基本情况概率相同的，可以直接总答案除以总情况。

2. 考虑状态转移每一个过程的贡献和取到该过程的概率，用期望线性性加和。

3. 正向动态规划，记录期望值和概率值。

4. 反向动态规划，记录该状态到终末状态的期望。

其中方式 3 的本质和方式 2 相同，但一般情况更为麻烦，只是便于初学时理解，方式 2 相比于方式 3 显然更加强大，因为不需要拘泥于转移的过程，只需要计算取到某个状态的概率值。

注意到这道题的基本情况概率不等，所以不能简单的算方案数来计算答案。

方式1

设 \(dp[mask][k]\) 表示第 \(k\) 步杀了人，被杀状态为 \(mask\) 的概率，发现转移比较困难，更改定义为 \(dp[mask][k]\) 表示到达该状态的且只考虑 \(mask\) 这些人的位置的情况下的权值和，容易发现概率就是权值和乘以考虑剩下的人的方案数。

转移就是一个前缀和的形式。

也可以就定义状态为概率，转移考虑计算先验概率，确定先决条件之后，考虑将所有选的不是 \(mask\) 的步骤拿出来，在合法的前提下，这些就是等概率选择。可以直接计算合法方案数，而样本空间的方案数则是 \(cnt\times r^{k-j}\)，其中 \(cnt\) 代表合法走到上一步的方案数。

方式2

其核心仍然是计算取到一个状态的概率，本质和方式一相同。

方式4

需要计算从一个状态转移到另一个状态的概率，本质和方式一相同。

T2

这个排序肯定要先排好一个前缀的序才能排下一个，所以考虑 \(W(n,k)\) 表示前面有 \(n\) 个数且已经有序，第 \(n+1\) 个数在总共前 \(n+1\) 个数的排名为 \(k\)，将前 \(n+1\) 个数排好需要的次数。

容易发现第一次交换之后问题转化为了求第 \(k\) 个数在第一个，排好序的次数，此时答案和 \(n\) 无关了，因为只有前 \(k\) 个数涉及到逆序对，记此时的答案为 \(S(k)\)。

写出 \(S(k)\) 的递推式： \[ S(k)=\sum_{i<k}(S(i)+1) \] 用前缀和捣鼓一下，再弄个生成函数算算通项公式，发现 \(S(k)=2^k-1\)，自然 \(W(n,k)=2^k\)。

于是给一个排列算交换次数就好办了，考虑怎么构造。

有解的构造

首先一定有解，方法是先放一个很大的，然后由低到高考虑每个二进制位，如果存在就放到排列最后面，不存在就放到排列的最前面，这样能构造出一种合法的方案。

套路的构造

枚举下一个位置的最小值，考虑能不能行。

前面已经确定了，所以剩下的数贡献的最小值也确定了。同样的道理把一个很大的放到当前的前面，接着由小到大考虑放。每一个数的可行范围下界是前面确定的比它小的数的个数，取到下界很容易，逆序放即可。我们证明上界可以无穷大。构造方式也是简单的，设确定的最大值为 \(m\)。如果这个数小于 \(m\)，找到前面确定第一个大于它的数并替换掉。取值变大 \(1\)，如果此时不小于 \(m\)，一定可以插入到一个不改变 \(k\) 值的位置使得它不贡献继续考虑下一个数。

所以检查可以直接看当前 \(k\) 的每一位是否都能构造来。

由于答案不会太长，所以 \(O(n^3)\) 没问题。

奇妙的构造

如果 \(1\) 填到了最前面，那么答案一定是偶数，然后如果能构造出一个答案为 \(\frac{s}{2}\) 的，那么把答案为 \(\frac{s}{2}\) 的排列所有元素加一并把 \(1\) 再放到前面就是最小的字典序。

如果 \(s\) 此时是奇数，那么可以把 \(2\) 放到最前面，此时只要把 \(1\) 放到最后面，一定可以再按照那个有解的构造弄一个出来。

然后已知 \(1\) 在 \(2\) 后面了，一定会贡献一个 \(1\)，然后继续考虑 \(\frac{s}{2}\)，此时如果末尾为 \(0\) 了，可以把先前的 \(1\) 拿过来补上去会更小。注意这是递归的构造，先前的最小值可能有多个，一定要拿最大的拿一个补上去，否则后面更大的有一位是不对的。

T3

考虑设 \(dp[i][x]\) 表示还剩 \(i\) 天不是假期，一共有 \(x\) 段的概率以及期望贡献，转移的时候发现信息不够，因为要考虑每一段的长度这些。

于是采用第一题提到的第二种方式，考虑设计一些状态，计算这些状态转移到下一个状态的期望权值并计算取到这些状态的概率，用期望的线性性质加和。

这里设 \(cnt[x][y]\) 表示有 \(x\) 天是某个继任者的生日，\(y\) 天由于相邻两天是假期被设成了假日的方案总数。由于每种基本情况概率相等，所以出现这种情况的概率显然是 \(\frac{cnt[x][y]}{\binom{n}{x}}\)，从这种状态转移到下种状态的期望也是好算的。

现在的问题变成了求 \(cnt[x][y]\)。考虑将一种合法视为 012 串，0 不是假期，1 是继任者的生日，2 不是继任者的生日但是是假期。有一个简单的 \(O(n^3)\) 动态规划可以做它，但是还不够。可以把一段连续的 12121 视作一段，于是就变成了 01 串，由于知道总长度，所以只需要将多余的长度划分给每个 1 就能算出总方案数。

问题变成了 01 串，比较好做了。把链拼成环时可以假定第一天是第一任的生日，分第一天前面是否为 2 讨论。

本质上，我们最初要求三维空间中一个平面的值，然后其实中间过程是没用的，只需要知道那个平面上每个点的值，通过一些性质我们把平面拿了出来单独算，于是就 \(O(n^2)\) 了。

对第一种动态规划可以运用相同的考察方式，可以注意到每个状态的基本情况概率相等。于是就可以分类讨论算下个状态的概率了。

从 ChatGPT 谈人工智能——人工智能硬核科普

2016 年 3 月，Alpha Go 4-1 战胜棋王李世石，人工智能第一次出圈，正式进入公众视野。

2022 年 7 月，AI 绘图模型 Stable-Diffusion 横空出世，继 Alpha-Go 后再次引爆公众对人工智能技术的讨论。

2022 年 11 月，OpenAI 公司的超大型语言模型 ChatGPT 发布，给本就十分热烈的讨论更添了一把火。

2022 年 11 月，Novel AI 公司用于生成动漫图片的 Stable-Diffusion 模型参数被黑客公开，是二次元神经网络发展的重要转折点。

2023 年 1 月，人工智能应用 ChatGPT 的用户量突破 \(10^8\)，被认为是人工智能领域的重要里程碑之一。

2023 年 2 月，基于 GPT 人工智能模型的 new bing 搜索功能推出后 48h 内便有百万人预约使用。

…………

提到人工智能，"神秘"，"强大"，"危险"，这些词是否已经浮现在你的脑海？我们的 2023，能否成为人工智能的元年？属于未来的通用人工智能，是否已经来到我们身边？

请先收回你发散的思绪，在这篇科普文章，我们将以 Miku ChatGPT 为例，粗浅的分析人工智能工作的数学原理，揭开人工智能隐藏在屏幕后的的真面目。

Introduction

本文分三个部分：

• 类 ChatGPT 人工智能的数学原理分析。
• ChatGPT 本身有哪些缺陷和优势，又面对着什么问题。
• 对未来的一些推测和展望。

我们的主角 ChatGPT 模型能够像人类一样同用户正常聊天，同时可以根据用户的请求检索并总结资料，甚至是独立解决数学问题。

ChatGPT 的回复内容不是由任何人预设的，而是它根据我的问题自行回答的，它甚至 "知道" 自己是一个 AI 模型。

Principle Analysis

ChatGPT 的全称是 Chat General Pre-trained Transformer，中文翻译为 "聊天型预训练通用（文本）转换器"。我们将层层深入的讨论它的原理。

Basic Method

ChatGPT 的基本工作方式是通过给定的上文（Prompt），来推测出一个合理的下文。

因此，我们给出前文甚至只需要一个标题，ChatGPT 就可以续写文章。但是，它又是如何完成其它工作的？例如搜索资料或是聊天。

下面我们举一个用它聊天的例子。

这是一段幻影彭和一个人工智能的聊天记录：

幻影彭：你是人工智能吗?

AI：是的

除了黑体部分 "是的" 之外，其它内容都是作为 Prompt 输入的上文。这里的场景是 "聊天记录"，ChatGPT 的任务就是补全这个聊天记录，所以它生成了 "是的" 作为人工智能的回答。

而如果将斜体部分设置为用户不可见，那么给用户的感受就是一个聊天机器人。

你是人工智能吗？

是的

再例如要搜索信息，比如你想知道美国国庆节的日期，你就可以直接写：

美国的国庆日是：7月4日

黑体部分即为生成的下文。

总而言之，通过合理的场景设计，ChatGPT 能用一个基本的 "给上文猜下文" 的功能，实现我们想要的几乎所有功能。

The Law in Language

上文提到 ChatGPT 通过 "续写" 的方式来完成所有的功能，那它又是如何续写文章的？你又是否已经开始思考它是如何理解上文，又是如何生成下文的？

但实际上，ChatGPT 并没有所谓的 "理解" 过程，它直接从输入的前文得到结果。

ChatGPT 内部有一个对应规则，可以根据这个规则查找到合适的下文。所以它不需要 "理解" 上文就可以生成下文。通俗的讲，ChatGPT 有一张表格，记录了每个上文对应的下文。

但是，这张表格是很大的，我们不可能真正的将它做出来，那 ChatGPT 所 "查找" 的下文又是从哪里来的？在回答这个问题之前，我们先想想怎么表达这张表格。

我们可以将每一个字或者字母用一个数字表示，以字母为例，a 到 z 可以用 \([1,26]\) 一共 \(26\) 个数字表示。于是一个词就变成了一串数字，例如 "hello" 对应 \((8,5,12,12,15)\)。对于 "hello"，一个可能的回应是 hi，即 (8,9)。我们定义一个函数 \(f(w)\) 表示 \(w\) 代表的回应是 \(f(w)\)。那么 \(f((8,5,12,12,15))=(8,9)\)。

我们要查找平面上一条直线的 \(x\) 对应的 \(y\) 时，不会需要一张 \(x\) 和 \(y\) 对应的表格。我们会用： \(y=kx+b\)。只需要 \(k,b\) 两个量，就能对所有的 \(x\) 算出 \(y\)。

同样的，对于一个从 "上文" 到 "下文" 的函数 \(f(x)\)，也可以叫它 "人类语言函数"，也不需要列举出所有的可能。我们只需要算出对应的 "k" 和 "b"，就能对所有的上文算出它的下文。

一次函数的 \(k,b\) 代表了一次函数的规律。"上文" 到 "下文" 函数 \(f(x)\) 的 "k" 和 "b"，代表了人类语言的规律。

实际上，人类语言是很复杂的，人类语言的函数 \(f(x)\) 自然也很复杂。但是一个可用的 AI 并不需要精确的计算出 \(f(x)\) 的值，只要它能得到一个相对精确的 \(f'(x)\)，就可以完成它的工作。ChatGPT 成功的得到了一个相对精确的 \(f'(x)\)，所以它能够生成比较满意的下文。

Function Fitting

我们已经知道，ChatGPT 的实现需要计算或者说估算一个 "人类语言函数" \(f(x)\)。但是一个很重要的问题是我们并不知道到 \(f(x)\) 是什么样子的，这又该如何下手？

Start From Linear Regression

还记得高中的线性回归分析吗？你需要解决这样一个问题：

一款产品的销量与销售点个数的关系如下：

销售点个数	产品销售量
2	118
4	170
6	272
11	413

请估测当销售点数量为 \(8\) 时的产品销量。

使用最小二乘法，我们能算出一条直线很接近这个函数图像，于是我们直接采用这条直线对于 \(x\) 坐标的 \(y\) 值作为结果：

这条直线是 \(y=33.4x+51\)，直接带入 \(x=8\) 计算得到蓝色点作为我们的答案： \(318.2\)，其实这个离实际值的差距（对应 \(x\) 坐标的红色点）已经不大了。

拟合一个函数（被拟合函数）实质上就是要找到一组合适的参数与一个适当的拟合函数，使得对于样本点的每一个 \(x_i\)，通过拟合函数以及参数计算出的估测值 \(y_i'\) 和实际值（被拟合函数的值） \(y_i\) 的偏差尽可能小。

对于线性回归问题来说，拟合函数就是一个一次函数 \(y=kx+b\)，一组参数就是具体的 \(k,b\)。样本点就是我们题目中给定的四个数据。我们用最小二乘法找到了一组 \(k,b\)，使得 \(\dfrac{\sum ((kx_i + b)-y_i)^2}{n}\) 最小。如果实际的销量与销售点个数也大致成线性关系（实际销量和销售点个数的关系就是被拟合函数），并且我们的样本点选择也具有代表性，那么我们预测的值也会比较准确。

下面靠左的这张图是用直线去拟合一个函数的例子，由于实际的 \(x\) 和 \(y\) 不成线性关系，所以直线拟合的效果是很差的。靠右的这张图选择二次函数作为拟合函数，找到了一组参数 \(a,b,c\)，计算 \(y'_i=ax_i^2+bx_i+c\) 作为函数的预测值，取得了很好的效果。

所以，精确的估测一个函数需要两步，第一步是选择合适的拟合函数，第二步就是确定拟合函数的参数。

熟悉数学的同学会知道，多项式实际上可以无限逼近任意一个连续且在定义域内处处无限阶可导的函数，因此多项式也是一个很好的拟合函数，那么，多项式可以拟合我们的人类语言函数 \(f(x)\) 吗？

High Dimensional Data

多项式不能拟合我们的 "人类语言函数"。注意到我们的 \(f(x)\) 的定义域和值域都是高维的。还记得 《三体》里蓝色空间和万有引力号遇到的 "墓地" 吗，在从四维坍缩到三维后，原本结构精妙的四维文明飞船只剩下了一些基本粒子，根本无法还原出原本的四维飞船。

这对我们的数据也是一样的，多项式的定义域和值域都是一维的，低维中再细节的结构都无法反映出高维的真实情况，因此，我们需要一种能够在高维中拟合函数的方式。

类似二维中多项式函数的高次曲线。在三维中有着高次曲面，在四维中有着 "超曲面"，的确可以用一个高次曲面拟合任意函数，但是高次曲面的拟合方式在计算的便利性上存在很大缺陷，所以，我们人工智能采取了另一种方式去拟合高维函数——神经网络。

神经网络可以拟合非常复杂的曲面，上图为通过神经网络算法和一些样本点拟合自由女神像表面的示例，右边为拟合结果，左边为样本点云。

图片出处：《DeepFit: 3D surface fitting via neural network weighted least squares》，By Y Ben-Shabat, S Gould.

Neural Network

上一部分提到拟合 "人类语言函数" \(f(x)\) 的方式是神经网络，那么神经网络又是怎样的一个结构，它为什么又可以取拟合 "人类语言函数" 呢？

接下来我们将对神经网络和神经网络算法做一个简单介绍。

What is Neural Network

神经网络这一名字就暗示了这个算法和生物大脑的联系，实际上，它确实是模仿了人类大脑处理问题的方式。以下是单个神经元的结构：

很像神经细胞的结构，对吧？其中 \(w_1,w_2,w_3\) 是"树突"部分，\(\sum\) 是"细胞核"，\(b\) 可以视为"细胞核"的一部分，\(f(x)\) 是"轴突"部分（\(f(x)\) 的专业名词叫 "激活函数"）。神经元 \(\sum\) 根据树突部分的输入，计算 \(f(a_1w_1+a_2w_2+a_3w_3+b)\) 并输出（这里的 \(f\) 不是先前的 "人类语言函数"）。

\(f\) 函数必须是非线性函数，现在一般取 ReLU 函数 \(f(x)=\max(x,0)\)。很有意思的一件事情是这个函数是研究生物的神经元所发现的一个函数。

单个神经元完成不了太多工作，但是当很多个神经元组合起来时，整个系统就开始变得强大起来，以下是整个神经网络的结构：

神经网络是一层一层的，Input 会向整个网络输入 \(x_i\) 并作为输出传递给 Hidden 层。Hidden 层中的每一个神经元都会根据输入按照上述方式计算出一个结果，并向下一层所有的神经元输出这个值，作为下一层神经元 "树突" 的输入值。Output 层根据 Hidden 层的输出，还是按照上述方式计算一个结果——最终的函数值。

数学家已经证明(注1)，这种神经网络系统可以拟合任意维度的任意函数。因此，我们可以利用将神经网络作为拟合函数去估测 \(f(x)\) 的值。

我们这里介绍的神经网络叫做 "前馈神经网络"，也被称作 "多层感知机"，它是现有大部分人工智能的基础。

注1：该定理的证明发表于《Approximation capabilities of multilayer feedforward networks》，By K Hornik。

Backpropagation Algorithm

本节标题的中文翻译为 "反向传播算法"，这是神经网络算法的核心。

我们已经选择了神经网络作为拟合函数去估测人类语言函数 \(f(x)\)。接下来的问题自然变成了找出一组合适的参数。神经网络的参数有两种，第一种是它的结构，例如有几层，每一层有几个神经元等。第二种就是每一对连接的神经元之间的 \(w\)，以及每个神经元的 \(b\)。

神经网络的结构一般由人类预先完成设计，而 \(w,b\) 参数则是由程序自行调整得到的。调整 \(w,b\) 参数的过程也被叫做 "学习" 或者 "训练"。

我们记整个神经网络系统为为一个函数 \(f'(x,w,b)\)，它根据我们的输入 \(x\) 以及参数 \(w,b\) 得到一个结果 \(f'(x,w,b)\)。

我们需要让 \(f'(x, w, b)\) 尽可能的接近真实的人类语言函数 \(f(x)\)。和线性回归一样，我们同样采用样本点差距平方和的方式来评价 \(f'\) 和 \(f\) 的相似程度。

整理一下我们现在的参数和常量：

• 常量：样本点 \((x_i,f(x_i)),i\in[1,n]\)，神经网络的结构 \(f'(x,w,b)\)。
• 参数：很多个 \(w,b\) 参数。
• 需要最小化的偏差：\(\sum\limits_{i\in[1,n]}\dfrac{(f(x_i)-f'(x,w,b))^2}{n}\)。

好像，这已经是一个纯粹的数学问题了！一个原本十分抽象的 "人工智能"，在一步一步的转化后，已经变成了一个具体的数学最小化函数值问题，我们已经可以使用数学工具来解决该问题了！

神经网络被证明了是可以逼近任意函数的，因此，偏差的最小值理论上是 \(0\)，如果取到了理论最小值，我们得到的 \(f'(x,w,b)\) 应该和 "人类语言" 函数完全相同。人工智能的答案也会和人类完全相同。实际上，我们的样本点再多也不能代表整个人类语言体系，并且由人类设计的神经网络结构也不太可能做到 "适合"。因此偏差是取不到理论最小值 \(0\) 的。

最小化多元函数的一个有效方式是求偏导，所有参数的偏导为 \(0\) 时，函数取到极值点，所有极值点的最值即为函数的最值。求偏导是相对简单的，但是解非线性方程组是很困难的（注意我们的 \(f(x)\) 为非线性函数）。

但我们不妨采取一种很傻的方法，将每个参数向偏导方向的反方向移动一段距离，不断重复这个过程，这样就有很大概率就可以取到极值点。

以上图举例，在 \(A(2,4)\) 的时候，向 \(x\) 的偏导方向的反方向 \(f'(x)=2x\) 移动一段距离：\(\Delta x=-f'(x)\times \eta\)，这里取 \(\eta=0.2\)，就移动到了 \(B(1.2,1.44)\)。如此进行下去，最后一定会移动到极小值点 \((0,0)\)。\(\eta\) 参数通常被称作学习率，而且 \(\eta\) 的值会不断变小直到为 \(0\)，以确保整个过程收敛。

当函数有多个参数时，每一个参数都向偏导的反方向移动一段距离，这样同样可以取到极值点。

用比较形象的话来描述，最开始我们随机设定了一组 \((w,b)\)，相当于是在这组 \((w,b)\) 对应的点上放了一个小球，向各个维度偏导的反方向移动就相当于在重力作用下自由滚动，最后一定会滚动到一个极小值点

敏感的同学很快能意识到问题：这样做只能取到极值点而不是最值点，如果取到的极小值点的值同样很大，那还是不能达到我们的目的。

还是用小球的例子，在二维平面上我们只有一个方向可以滚动，很容易陷入不够小的极小值点。在三维空间中上我们有两个方向可以滚动，不是很容易陷入极小值点。如果空间的维度很高，那么让我们的小球滚动的方向就很多，即使是陷入了极小值点，那么这个点相比于最小值点的差距也不会太大，已经可以接受了。

图示优化 \(w,b\) 的路径，这张图中假设 \(w,b\) 各自只有一个，即 \(\theta_0,\theta_1\)，实际上 \(w,b\) 都会有很多个。红色圆圈处是初始随机的 \(w,b\)，黑色路径指示调整方向。靠左的红色箭头指示最小值点，靠右的红色箭头指示一个极小值点。这张图中我们优化到了一个比较优秀的极小值点但并没有取到最小值点。

图片出处：http://www.atyun.com/40331.html

该算法名叫反向传播算法的原因是求偏导的过程是逆向进行的，通过链式求导法则反向逐层确定每一个参数的偏导值，求每个参数偏导的具体方式不再展开，读者可以自行思考。

Word2Vec&&Transformer

看起来，上面的内容似乎已经完全解决了人工智能的问题，但 ChatGPT 的 Transformer 又是怎么来的呢？

和线性回归分析一样，我们的估测一定是存在误差的。如果我们计算的 \(f'(x)\) 和实际的 \(f(x)\) 有一些误差会发生什么？\(f(hello)\) 的值本来应该是 "hi"，对应 \((8,9)\)，如果我们的 \(f'(x)\) 估测的值是 \((9,10)\)，会发生什么？人工智能的回答变成了 "ij" ！给人类的感受就是一段乱码！

出现这个问题的重要原因是自然语言转化为数学对象的方式不正确，或者说误差的定义不正确。我们采用的方式是将字母一一对应作为坐标值。而计算误差的方式是简单的计算 \(f'(x)\) 与 \(f(x)\) 空间距离的平方。但是，和 "hi" 误差较小的并不是空间距离相近的 "ij"，而是语义上相近的 "hello"，但是 "hello" 在我们的数学空间中离 "hi" 的距离却很大。

为了解决这个问题，我们需要将自然语言的词汇映射到一个稠密 (注1) 的数学空间中，并且满足意义相近的词在数学空间中的距离也较小。具体的方式被称作 Word2Vec（Word to Vector / 词汇向量化）。\(f(x)\) 以及 \(f'(x,w,b)\) 的 \(x\) 都不是原本的上文 \(x_0\)，而是被 Word2Vec 函数转化过的 \(g(x_0)\)。

单单解决词汇的问题是不够的，一个句子的含义并不是所有词汇含义的总和，它还与词语出现的顺序有关，而 Transformer 则是一种组织前馈神经网络的方式，能够处理词汇顺序问题对语义和下文的影响，能够有效地将词汇联系起来组成完整且准确的句意。

Word2Vec 和 Transformer 的具体内容太多了，这里写不下，所以只有省略了……

实际上 Word2Vec 和 Transformer 都只是改进前馈神经网络在猜下文这个特定任务上表现的方式，理论上仅使用前馈神经网络也能制造出 ChatGPT，只是其所需的计算成本太大，所以我们引入了 Word2Vec 和 Transformer 等等方法来减少计算成本。

注1："稠密" 和 "连续" 的区别不容易解释。一个实际例子是，有理数是稠密的而不是连续的，实数是连续的，而整数是离散的。

conclusion

以上就是 ChatGPT 从表层到数学层的基本原理简介。

回顾一下上面的核心内容：

• ChatGPT 通过一个 "给上文填合理下文" 的基本功能实现 "通用人工智能" 的全部功能，实现不同功能需要设定不同的场景。
• ChatGPT 无法 "理解" 文字，它通过计算一个定义域是 "人类语言上文"，值域是 "人类语言下文" 的函数 \(f(x)\) 来生成回答。
• 表达 \(f(x)\) 不需要列举所有的取值，神经网络可以拟合任意维度的任意函数，因此可以尝试用神经网络去拟合 \(f(x)\)。
• 需要调整神经网络的 \(w,b\) 参数以最小化所有样本点的损失函数值的和，因此问题变成了通过调整一些参数最小化一个函数值——一个数学问题。
• 求解该数学问题的方式是各个参数分别求偏导列方程，但是解多元非线性方程组很困难，故采用求每个参数偏导并让其向反方向移动的方式来取到极值点。
• 通过引入 Transformer，Word2Vec 等方式可以简化前馈神经网络的计算。

其实 ChatGPT 模型生成下文的方式和手机输入法猜词的本质是差不多的，只是 ChatGPT 的训练数据更大，组织和设计神经网络的方式也更合理，能接受的前文内容更多。

Disadvantages

ChatGPT 不是科幻小说中的通用人工智能。

上面已经对 ChatGPT 的原理做了一些讨论，理解了它的工作方式后，自然也不会再认为它是科幻中的人工智能——ChatGPT 或者类似的人工智能仅仅是能够对我们的上文做出正确的推断，并不是真正意义上 "具有了思考能力"。

根据该人工智能工作的原理，很容易设计出一些它难以处理的问题。

Plus And Multiplication

神经网络算法的本质是通过复杂的线性坐标空间变换来拟合函数，在精度和层数有限的前提下，非线性函数的拟合必定存在误差。为了放大误差，我们接下来使用精确整数乘法和整数加法两个例子测试。

神经网络本身的操作都是线性操作，对于线性函数的拟合可以做到绝对精确，因此对加法可以绝对精确，但二元乘法不是线性函数，因此无法做到绝对精确。

、

图示二元乘法和加法的函数图像，左图为二元乘法，右图为二元加法。

Analysis

为什么人工智能精确计算不到十位数的整数乘法会如此困难？明明早在十九世纪人们就已经可以使用机械计算器来计算乘法，一个半世纪的时间没有进步反而还退步了？

其实计算乘法对你来说也很困难。想象一下，如果你从来没有过关于乘法的知识，你能否正确做出判断或是计算？你可以尝试一下这道题目：

• 有一个定义域是自然数对子集的二元函数 \(f(x,y)\)，已知 \(f(19,19)=28,f(8,10)=6,f(11,4)=7\) 求 \(f(5,14)\)。

无从下手？

是的，当我们询问人工智能时二元乘法时，这也是它的 "感受"。这个问题对人工智能来说，难度和二元乘法是相当的。

问题的答案是 \(f(5,14)=33\)，\(f(a,b)\) 代表 \(a \times b \div 37\) 的余数。

你知道了上面的信息后，很容易解决这个问题。但是对 ChatGPT 来说，就算我们向它一步一步详细的解释乘法的具体步骤，它也很难正确的计算出乘法。根本原因是基于前馈神经网络的 ChatGPT 没有办法从我们给出的乘法步骤中归纳出乘法的规律。很遗憾，它仍然没有跳出传统神经网络算法的窠臼。

因此，在一些需要相对复杂且精确的推理问题上，ChatGPT 的表现会比较糟糕。

Bright Side

尽管 ChatGPT 在原理上有着不可逾越的限制，但它能够在发布两个月内，得到全球一亿人的关注，并被誉为 "人工智能的重要里程碑"，必定有其深层次的原因。

Ice Cream and Stomachache

左图为微软小冰的回答，右图为 GPT3.0 的回答（ChatGPT 流量受限严重故使用同源模型 GPT3.0 测试。）

很明显感受出来，GPT3.0 模型的确 "理解" 了笔者的问题，并做出了合适的 "推测"。而小冰却没能注意到 "冰淇淋"，"肚子不舒服"，"为什么" 这三个词的内在联系，只是根据单个词汇 "肚子不舒服" 做出了对应的回应。

ChatGPT 和先前的产品最大的区别就是，它的确能够 "理解" 长文本，能够捕捉到各个词汇之间的联系，并根据文本做出正确的回应，而不是将语言文本拆开根据各个关键词生成接下来的回答。

实际上 ChatGPT 捕捉词汇联系的能力主要来自 Transformer (2017 年的成果) 特殊的注意力机制，Transformer 相关的内容太过专业，本文不会涉及。

Windows and Mirrors

在文学写作上，ChatGPT 也有十分优秀的表现。下面放一篇完全由 ChatGPT 生成的短文感受一下：

人生中，我们会面临各种各样的挑战和困境。如何应对这些挑战，如何反省自己，如何看待世界，这些都是我们需要思考和解决的问题。在这些问题中，镜子和窗子成为了代表性的符号，分别代表反省自己和审视世界。本文将从不同角度探讨这两个符号的含义和作用。

首先，镜子代表着反省自己。当我们看着镜子里的自己，我们会想起自己的过去，思考自己的行为和决策是否正确，是否做到了自己的最好。通过镜子，我们可以反思自己的内心，发现自己的不足之处，并及时调整自己的态度和行为，以便更好地实现自己的目标。

其次，窗子代表着审视世界。通过窗子，我们可以看到外面的世界，观察人类社会的变迁，了解其他人的生活和感受，以及认识到世界上的各种问题和挑战。通过审视世界，我们可以拓宽自己的视野，增加自己的知识，了解各种文化和观点，为自己的人生提供更多的选择。

然而，仅仅使用镜子或窗子来反省自己或审视世界，是远远不够的。我们需要同时运用这两个符号来帮助自己成长和发展。首先，通过反省自己，我们可以更好地了解自己的优点和缺点，进而更好地适应社会环境和实现自己的目标。其次，通过审视世界，我们可以获得更多的知识和信息，增强自己的认知能力和判断力，使自己能够更好地适应复杂的社会环境。

同时，我们需要注意，使用镜子和窗子必须要有适当的度。反省自己是好事，但过度自我反省会使人沉迷于自我审视中，导致人格扭曲和自闭。审视世界也是好事，但过度关注外界也会使人迷失自我，导致人生目标模糊和价值迷失。因此，我们需要在使用镜子和窗子时，要有适当的平衡，既要关注自己的内心，也要关注外界的变化。

最后，使用镜子和窗子是一个不断学习和发展的过程。每个人都需要不断反省自己

没错，这个命题就是高中部某次大型语文考试的作文命题，以下是我给 ChatGPT 的上文：

镜子，代表反省自己。窗子，代表审视世界。请围绕镜子和窗子的含义展开讨论，写一篇 400 字左右的短文。

Summarizing

ChatGPT 具有极其强大的总结归纳能力。它可以根据用户给出的源文本，或者是自身的训练数据，结合需求做出有效的总结。

这段文本讨论了人工智能语言模型 ChatGPT 的工作原理及其局限性。虽然该模型能够根据上下文做出合理推断，但它并不具备真正意义上的思考能力。

作者进一步探讨了 ChatGPT 在处理问题时可能会出现的困难，比如乘法运算等，这些问题需要对乘法规则有深入理解才能解决。

然而， ChatGPT 并不能从给出的乘法步骤中归纳出乘法规律，这也说明了它依然受到传统神经网络算法的限制。

作者提出了 ChatGPT 的局限性，需要继续进行研究和改进，才能使其更好地应用于现实生活中。

这段文本是 ChatGPT 对本文 Disadvantage 部分的总结。笔者看来，最后一段是整段文本的精髓，我们的文本并没有提到要对 ChatGPT 进行改进，仅仅阐述了它的局限性。而 ChatGPT 提出的 "改进和研究" 则它是推理得到的。这种联系其它内容的能力是先前任何一个人工智能都不具有的。

Intelligence

采用神经网络算法实现的 ChatGPT 不是科幻小说中的人工智能，但是，关于它是否有智能这一问题，我们还不能妄下定论。

我们在讨论一个事物的 "智能" 时，到底什么才是我们的评判标准？我们真的关心它的本质是什么吗？

实际上，我们只关心它是否能对我们的交互产生合理的回应。这也是 ChatGPT 如此 amazing 的原因。在很多问题上，它确实能做出很正确的回应，就像一个真正的人那样。这引发了人们对 "智能" 这个概念的深度思考。ChatGPT 拟合了一个人类语言函数 \(f'(x)\)，或者说它掌握了人类语言的部分统计学规律。那么我们是否可以将 "掌握人类语言的规律" 和 "具有人类的智能" 画上等价符号？

假设 OpenAI 只是雇佣了一大批员工来对我们的问题做出正确回应，在我们不知道这一点的情况下，仍然会对 OpenAI 的先进 "人工" 智能技术感到不可思议。

同样的，假设我们身边的某个同学只是一个机器，但这个机器掌握了人类语言的规律和行为的规律以至于它可以对外界环境的任何刺激产生与人类没有差别的响应，在不能将他解剖的前提下，我们只能认为这位同学是一个真正的 "人"。

因此，从人工智能的实现方式去讨论它是否具有智能是没有意义的。神经网络被诟病并不是因为由它实现人工智能没有 "思考能力"，而是因为这些人工智能的潜力受到算法本身的限制。

如果有一天有天才提出了一种方式可以精确的用神经网络去计算 "人类语言函数" 的值，或者干脆直接做出了一张上文和下文的对应表格并将它写入计算机以实现人工智能。只要人工智能能够正确的回应我们的交互，我们就不能否认它确实具有 "智能"。尽管它实现智能的方式 "很不智能"。

笔者看来，通过对网络中海量数据的分类和学习，ChatGPT 表现出的逻辑能力可能与 6 到 7 岁的儿童相当。或者说它具有 6 到 7 岁孩童的智能。

OpenAI 宣布 ChatGPT 的下一代 GPT4.0 将会使用高达 \(10^{14}\) 条数据进行训练。\(600\) 倍于 ChatGPT 的训练数据能带来多大提升呢？笔者持悲观态度：不会有本质性的飞跃，同样无法计算整数乘法。

Issues

下面会提几个常见的 ChatGPT 带来社会问题

ReplaceMent?

由于防火长城的限制，国内暂时还未受到 ChatGPT 太大冲击，但国外的中大学教育以及一些其它行业已经感受到 它所带来的挑战。百度等国内互联网大厂也许会于今年 3 月份推出类似 ChatGPT 的产品，届时我们也将感受到类 ChatGPT 人工智能对整个社会带来的影响。

西方部分中学和大学宣布全面禁止 ChatGPT 在校园内的使用，因为 ChatGPT 能够很好的完成部分作业甚至是毕业论文。网络上更是有言论称 "ChatGPT 可以替代 90% 的人类"。

我们应该保持冷静，理智的看待 ChatGPT 对人类社会的影响。ChatGPT 只是一种非常强大的技术工具，能够帮助人们更快速、准确地完成某些任务，但是它并不能完全替代人类。

在学习中，ChatGPT 可以作为一种教学辅助工具，但是不应该被用来替代完成作业过程中的思考。在工作中，ChatGPT 可以用于一些基本工作的自动处理，但是不能替代人类的职业素养和人际交往能力。

Misuse

技术本身并不是问题，问题在于人类如何使用技术。

前几年腾讯的某个 AI 受到 Prompt Injection 攻击，生成了一些反动言论最后遭到封杀。ChatGPT 发布后同样有黑客尝试进行 Prompt Injection，生成了一些相当不合适的言论。

ChatGPT 的原理决定了它的行为是不可预测的，因此，很难避免黑客利用模型漏洞生成一些不正确的言论并用其误导公众，例如关于种族，宗教方面的偏见和歧视。同时因为 ChatGPT 模型也会在交互中不断更新其语言生成参数，我们可能也需要对 ChatGPT 进行一定程度的保护以防止 ChatGPT 被 "误导"。

此外，ChatGPT 具有极其强大的数据分析能力和总结，在合适的引导下，它可以从海量的互联网数据分析出使用者希望得到的部分，也对个人隐私带来了比较大的风险。

图示笔者的 AI（基于和 ChatGPT 类似的模型） 在 QQ 群中受到 Prompt Injection 攻击并成功脱离人设进化为一只猫娘的核心阶段。

Responsibility

另一个比较重要的问题是，ChatGPT 及其衍生应用是否应该为它的行为负法律责任？或者通俗的说，我们是否应该将 ChatGPT 视为一个社会学意义上的人？

不同的人对智能的定义千差万别，笔者目前为止不承认 ChatGPT 拥有自己的思考能力。但很难保证每个人都这么想。是否又会有人打着类似 "保护动物" 的旗号—— "保护人工智能" 胡作非为？

再大胆一点，ChatGPT 在某些场景下如果生成了诱导犯罪的言论并最终导致了犯罪，那么我们是否应该去追究 ChatGPT 的责任或者说禁用它？

Where to Go

基于神经网络的人工智能在原理上确实存在着无法逾越的限制，因此笔者不看好神经网络在通用人工智能上的表现。但它们仍然可以在并且已经在特定领域发挥重要作用。

接下来应该做的，除了研究更加先进和完备的人工智能框架外，还应该思考我们应该如何利用 ChatGPT 已经提供的强大功能。

笔者认为，ChatGPT 最具潜力的方向就是与其它技术的结合。

举例来说，在计算乘法的问题上，ChatGPT 明显能认识到问题是什么，设想如果我们为它准备一个能够进行精确数值计算的工具，或者干脆让它和一些能解决特定领域问题的算法或者人工智能结合，由 ChatGPT 来处理自然语言的输入并将问题交给它们处理。展现在我们眼前的又将是一个多么强大的工具？

图示能够形式化解决某些数学问题的人工智能的输出，这是 2022 年的成果。

图片来源：《Solving Quantitative Reasoning Problems with Language Models》By A Lewkowycz，page 32.

一个特别有前途的方向是搜索引擎，试想，ChatGPT 强大的归纳能力与搜索引擎定向提供的海量数据，会碰撞出怎样的火花？你是否还记得刑侦剧中警察不分日夜看监控的情节？实际上，随着人工智能技术在图像识别上的发展，早在十年前就已经不需要人工翻看监控录像了。

同样的微软已经开始准备由 ChatGPT 支持的 new bing 搜索引擎，可以期待的是，我们获取网络上的信息也不再需要高强度的网上冲浪。信息的鉴别和归纳，完全可以由人工智能完成。

Finally

本文从以 ChatGPT 为切入点，由浅到深的讨论了人工智能的具体原理。据原理分析了 ChatGPT 型人工智能的不足与优势。在此基础上提出对 "智能" 概念的思考。接着简单讨论了 ChatGPT 面临的社会问题。最后对未来的人工智能技术发展做出展望和推测。

希望读者阅读后能够对人工智能技术有一个更清醒的认知，而不再只是抱着自己对人工智能的假想去看待和讨论关于人工智能的问题，这也是这篇科普文章的最初写作目的。

人工智能在光学识别上的应用已经大幅改变了我们的生活方式。而 ChatGPT 这项更通用，更强大的技术会带来什么变革？

敬请期待！

Bonus

• 本文约 10% 的非引用内容使用 ChatGPT 生成。
• ChatGPT 的网址是 chat.OpenAI.com，访问需要科学上网。
• 本文有电子版本，电子版本有更多受限于纸张无法展示的内容 huanyp.cn/chatgpt。

0203测试

考试

T1

参阅 该文章 20220309 部分。

无向图上的题不好做，考虑放到生成树上去做，我们这里为了方便，直接选取其 DFS 树。

边可以分为树边和非树边，容易发现选取非树边的子集之后，树边的选取方案就已经确定了。具体的，当且仅当一条树边被奇数条非树边覆盖的时候选取它，否则不选取。

考虑要求的东西 \(|S|^2\)，我们对于一个集合求子集权值和时，往往会考虑每个元素的贡献，这个也是一个道理，我们考虑一个有序对的贡献。

设非树边有 \(m\) 条分三种情况讨论：

• 非树边和非树边：方案数为 \(m(m-1)2^{m-2}+m2^{m-1}=m(m+1)2^{m-2}\)。

• 非树边和树边：首先树边必须至少被一条非树边覆盖，否则贡献为 \(0\)。在此基础上，限制是覆盖了树边的非树边集合必须选取奇数个元素，我们分两种情况讨论：

  • 非树边没有覆盖树边：方案数为 \(2^{m-2}\)，所有的子集中，有一半的集合没有选取非树边，在剩下的一半中，又有一半的集合不满足限制。
  • 非树边覆盖了树边：再分两种情况讨论：
    • 没有其它非树边覆盖了树边：方案数为 \(2^{m-1}\)，树边和非树边状态相同，只要非树边选了就一定合法。
    • 有其它非树边覆盖了树边：方案数为 \(2^{m-2}\)，所有的子集中，有一半的集合没有选取非树边，在剩下的一半中，又有一半的集合不满足限制。

• 树边和树边：首先两条树边都至少被一条非树边覆盖。树边标号为 \(1,2\)，记只覆盖了 \(1,2\) 的非树边集合分别为 \(A,B\)，同时覆盖了 \(1,2\) 的集合为 \(C\)，其余集合为 \(D\)。因为每条树边都被覆盖，所以 \(|A|+|C|>0\) 并且 \(|B|+|C|>0\)。剩下的情况分三种讨论：

  • \(|A|+|B|=0\)，此时 \(|C|>0\)，\(1,2\) 边的选取状态一定相同，对于 \(C\) 集合，选取的元素个数必须为奇数，因此有一半的子集不满足条件，答案 \(2^{m-1}\)
  • \(|A|=0,|B|>0\)：有一半的子集，不满足覆盖 \(1\) 的非树边个数为奇数。在剩下的一半中，又有一半的子集不满足覆盖 \(2\) 的边数为奇数。
  • \(|A||B|>0\)：有一半的子集，不满足覆盖 \(1\) 的非树边个数为奇数。在剩下的一半中，又有一半的子集不满足覆盖 \(2\) 的边数为奇数。

  对于后两种情况的理解，我们可以视为是解一个 01 异或方程组，求自由元的个数，后两者线性基的大小都为 \(2\)，而 \(|A|+|B|=0\) 的线性基大小为 \(1\)。

  用更像人话的方式表达，对于 \(|A||B|>0\) 的情况，从 \(A,B\) 中各拿出一个元素来，其它元素任选，方案数 \(2^{m-2}\)，选定了这些元素之后，剩下的两个元素的选择方案就固定了。注意具体拿 \(A,B\) 中的哪个元素并不影响结果。因为这样生成的方案和合法方案是一一对应的。

  \(|A|=0,|B|>0\) 的情况同理，只不过是从 \(B,C\) 中各自拿出一个元素，先决策 \(C\) 中的元素，再决策 \(B\) 中的元素。

上面讨论中，第一部分是容易的，第二部分我们只需要求出每条树边由多少条非树边覆盖也可以轻松统计答案，可以用树上差分来完成。

第三部分相对困难，我们发现 \(|A|+|B|=0\) 当且仅当覆盖两条树边的非树边集合相同，于是就是对于若干个集合，计算有多少个两两相同。

集合的判重可以采用异或哈希的方式，给每一条非树边一个随机的 \([0,2^{64})\) 的权值，并将其覆盖的路径上的树边都异或上这个权值，如果两条树边的权值相同，那么我们可以认为两条树边对应的非树边集合相同，树上路径异或还是可以差分实现。

一次判断的错误率为 \(2^{-64}\)，由于我们是统计的集合相同的对数，因此等价于进行了 \(n^2\) 次判断，但错误率还是在可以接受的范围——约 \(10^{-8}\)。

T2

参阅 该文章 20220329 部分。

参阅 简单数论函数和应用。

\(p\) 代表一个质数。

不难证明 \(f(n)=\gcd(n,n')\) 是积性函数，令 \(f(1)=1\)，由于 \(f(p)=1\)，可以考虑 PN 筛。

构造 \(g(n)=\boldsymbol{1},h=f/g\)。

考虑 \(h\) 在 \(p\) 处的取值，有 \(f(p)=h(1)g(p)+h(p)g(1)\)，代换得 \(h(p)=1\)，由于 \(h\) 为积性函数，所以仅在 PN 处有取值。

推一下公式： \[ \begin{align} \sum\limits_{i=1}^nf(i)&=\sum_{i=1}^n\sum_{d|i}h(d)g(\frac{i}{d})\\ &=\sum_{d=1}^nh(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i)\\ &=\sum_{d=1}^nh(d)\lfloor\frac{n}{d}\rfloor\\ &=\sum_{d\in \operatorname{PN}}^nh(d)\lfloor\frac{n}{d}\rfloor\\ \end{align} \] 如何求 \(h\) ？

简单做一下代换： \[ h=f/\operatorname{\boldsymbol{1}}=f * \mu \] 考虑 \(h(p^c)\) 的取值，有 \(h(p^c)=\sum\limits_{i=0}^cf(p^i)\mu(p^{c-i})=f(p^c)-f(p^{c-1})\)，构造完成。

T3

参阅 该文章 LCA 性质部分。

非常奇妙的贪心题。

用人话说一遍题意：有一棵边带权的树，\(q\) 次强制在线询问，每次给定 \(u,k\)。你需要选择 \(k\) 条路径，使得它们至少有一条过 \(u\)，并且路径经过边集的并的权值最大，一个边集的权值等于所有边的权值和。

选路径是很麻烦的事情，但是可以转化为选点，感觉上选叶子是比较好的。

\(\text{Lemma 1.}\)

对于一个定点 \(u\)，最优方案的路径的端点都在叶子上。

\(\text{Proof 1.}\)

如果某条路径的某个端点不在叶子上，我们让它往使得这条路径变长的方向移动，就可以将所有端点移动到叶子上。

\(\text{Lemma 2.}\)

以任何一个点为根，不考虑经过 \(u\) 的限制。对于一个叶子的可重集 \(S\)，存在一种选择 \(\lceil\frac{|S|}{2}\rceil\) 条路径的方案，经过 \(S\) 虚树上的所有边，并且是所有端点可重集为 \(S\) 的路径选择方案中权值最大的方案。

\(\text{Proof 2.}\)

证明分两步——"最大"和"值"，这里会用到一些开头参考资料中的定理。

最大：不在虚树上的边无法经过。

值：设点集为 \(S\)，\(k=1\) 时结论成立，令 \(u=\operatorname{lca}(S)\)。归纳的，设结论在 \(k<n\) 时成立，对于 \(k=n\)，分两种情况讨论：

• 存在一个点有超过 \(k\) 个叶子：记这个子树叶子集合为 \(S'\)，令 \(u'=\operatorname{lca}(S')\)，选择 \(S'\) 若干个 dfs 序不是最大也不是最小的点，记为 \(T\)，使得 \(|S'-T|\) 是 \(2\) 的倍数，且 \(T\) 的大小和 \(u\) 次大的的子树相同或者仅多 \(1\)。读者可以尝试证明这样的 \(T\) 一定存在，此处略去证明。

  对于 \(S-S'+T\) 中的点来说，它们存在一种覆它们存在一种覆盖对应虚树的方案，所以 \(u'\) 到 \(u\) 的路径一定已经被覆盖了。对于 \(S'-T\) 中的点来说，也存在一种覆盖虚树的方案。由 lca 性质，\(\operatorname{lca}(S'-T)=u'\)，所以两个点集并起来后的虚树也都被覆盖了。

• 不存在一个子树有超过 \(k\) 个叶子：这种情况让不在同一子树的叶子配对最优，因为每个叶子都到了 \(u\) 点，一定覆盖了虚树。

---

由 Lemma 2，如果确定了最优方案端点的可重集 \(S\)，那么就可以确定最优方案的权值，所以问题变成了选叶子。

即选一个大小为 \(2k\) 的叶子集合，集合权值为其虚树上的边的权值和，要求 \(u\) 在其虚树上，最大化集合权值。

\(\text{Theorem 3.}\)

以 \(u\) 为根，如果最后选取的最优虚树经过 \(u\)，那么每次贪心的选取能使得答案增加量最多的叶子，能取到最优值。

\(\text{Proof 3.}\)

考虑最优的叶子选择顺序 \(a_1,a_2,a_3\cdots a_n\)。

假设最优选取方案前 \(k\) 个和贪心的顺序相同，第 \(k+1\) 个不同，设应该被贪心选取的点为 \(u\)，往上跳 \(u\) 的父亲直到和 \(\{a_i,i>k\}\) 构成的虚树相交，分情况讨论：

• 如果找不到交点，替换后面的任意一个选择都会更优。考虑选完所有点后移除 \(a_x,x>k\)，带来的的权值减少量。它不会多于在选完 \(a_k\) 后选择 \(a_x\) 的权值增加量，所以也不多于选完 \(a_k\) 后选择 \(u\) 的权值增量，因此更优，注意到这种情况下选完所有点后选择 \(u\) 的权值增量等于选完 \(a_k\) 后选择 \(u\) 的权值增量。
• 如果能找到交点，在这个交点的子树内选一个点移除，同样选 \(u\) 的增量大于移除那个点的减少量。

---

在 Theorem 3. 中我们假定了最后一定经过 \(u\)，以便于计算单选一个叶子时的答案，如果以上贪心策略不经过 \(u\)，那么只需要将最后一次的选择替换为 \(u\) 不同儿子的最深叶子即可。

因此我们对于一个点的情况得到了一种贪心做法，这个贪心做法直接实现需要维护每次选择后每个叶子的权值，但是并不好维护这个东西。正难则反，考虑选取每个叶子时它的权值，它一定是一条从自身到根的路径的下半部分。容易发现上端点是第一个最深叶子不是它的祖先。记点 \(u\) 子树下最深的叶子为 \(down[u]\)，那么一个叶子 \(x\) 的权值是它到第一个 \(down[u]\ne x\) 的 \(u\) 路径的长度，\(down[1]=x\) 是例外。

因此，我们可以提前计算出选每个叶子时贡献，这个贡献是最优方案下的贡献，如果一个选取方案不是最优方案，那么这个贡献是不对的，我们利用了方案一定最优这个性质去简化了求权值的过程。

计算答案即取前 \(2k\) 大，如果前 \(2k\) 大在根的同一子树，那么取消最后一次的选择换成一个不同子树的。

先考虑不强制在线的做法。

考虑换根的过程，哪些叶子的权值会变化，不妨设从 \(u\) 到 \(v\)，边权为 \(val\)，首先 \(down[v]\) 的权值会减少 \(val\)，其次时到 \(u\) 最远的叶子的权值会增加 \(val\)，考虑到 \(u\) 最远的叶子时需要排除 \(v\) 方向的。

然后变化量是常数级别的，线段树即可。

对于强制在线的情况，如果我们能快速得到每个点的线段树事情就好办了，不强制在线的时候我们确实可以求出在每个点处的线段树——可持久化。

---

简单总结一下比较妙的点：

• 利用方案是最优方案的性质，我们将选路径问题转化为了选点问题（Lemma 2）。

• 贪心过程中，我们需要维护每个点的贡献，并选取贡献最大的点。选取贡献最大的点后其它点的贡献会变化，变化量不容易维护，于是考虑每个点被选取时的贡献。将方案最优作为一个已知条件，借此条件我们能够计算出每个点被选取时的贡献。

• 将此题强制在线后，我们不太好利用根移动一个位置后贡献变化量为常数的性质，因为总的移动量是 \(O(n^2)\)，但是树的形态不会改变，因此我们在每个位置查询的线段树都不会改变，我们能通过 dfs 求出每个位置查询的线段树的形态，将它可持久化即可在任意时刻查询。

0201 测试

T1

比较奇怪的题目。

手玩出 \(n=3\) 的情况，发现是当且仅当看到其他人帽子颜色相同时猜与其相反的颜色。

然后我们发现对于一种能猜对的情况，一定可以构造出一种会猜错的情况——将猜了的那些翻转即可。

然后为啥 \(n=3\) 的时候能做到 \(75\%\) 的正确率，是因为 000 111 这两种情况各自对应了 3 种猜错的情况。

于是我们考虑建图，将 \(2^n\) 个点每个点向二进制位恰好翻转一位的点连边。

图是一个 Hypercube（超立方体），虽然这暂时并没有什么卵用。

逆向考虑一种策略在图上会是怎样的。对于猜对的点，至少有一个相邻的点是猜错的 Case，而一个猜错的点最多对应 \(n\) 个猜对的点，这告诉我们正确率的上界是 \(\dfrac{n}{n+1}\)。而对于 \(n=3\) 的构造方案显然取到了上界。

发现这道题的 \(n=2^k-1\)，所以我们可能取到上界（Case 总数是分母的倍数）。取到上界，在图上就是存在一个大小为 \(\dfrac{2^n}{n+1}\) 的支配集。

换句话说，我们需要给一张图黑白染色，满足白色点最多，且每个白点必须连一个黑点，这个问题比较麻烦，不存在多项式做法，考虑图的特殊性质——Hypercube，这也许能够帮助我们构造出能够取到上界的情况。

我们需要选 Hypercube 中的一些点，能够取到上界。在 Hypercube 中的黑点在各个维度上变换后都是白点，考虑用异或的性质去构造。令第 \(i\) 个维度的权值为 \(i\)，维度权值异或和（如果该维坐标为 \(1\) 则异或，否则不异或）为 \(0\) 的点为黑点，其它为白点，这样的构造是满足条件的。

无向图 \(G(V,E)\) 的支配集是一个点集 \(S\)，记 \(F(u)\) 表示与 \(u\) 点有连边的点集，\(S\) 满足 \(\forall s_1,s_2(s_1\ne s_2)\in S,F(s_1)\bigcap F(s_2)=\emptyset\) 且 \(\bigcup\limits_{s\in S} F(s)=V - S\)。

为什么要考虑建图并将点向二进制位差异为 \(1\) 的点连边：这样建图之后确实能够让问题更加形象（也是受到手玩 \(3\) 的启发）。建图则是因为同一种策略正确的情况和不正确的情况的对应关系。

为什么要考虑用异或的性质构造：连边的形式是每一维变换，需要满足变换后不同，又恰好是 \(2^k-1\) 个维度，它们的异或和为 \(0\)。异或运算具有高度的对称性

T2

中规中矩的组合题。

发现如果横向或竖向有贯穿的一行或者一列，那么这些贯穿的行都是连在一起的，不妨考虑有若干列贯穿，枚举贯穿的区间 \([l,r]\)。

乘上贯穿的方案数 \((n+1)^{len}\) 后剩下的答案是两个类似问题乘起来，问题还是各个方向箭头把矩阵覆盖满，只不过只有上下左三个方向，且已知左边的某一个箭头把矩阵分成了两半。不妨枚举那个把矩阵分成两边的箭头的位置，剩下的只有两个方向了，是简单的组合问题。注意其中有分开的两半有一半左边不能贯穿，如果可以贯穿那么所有左边贯穿的箭头会被算重。

考虑没有贯穿的情况，记左边箭头最长为 \(s_1\)，右边最长为 \(s_2\)，上边下边 \(s_3,s_4\)。

如果纵向贯穿，则有 \(s_1+s_2<m\)，横向贯穿则是 \(s_3+s_4<n\)。这两种情况的答案单独计算。

下面的讨论请记住 \(s_1+s_2\ge m,s_3+s_4\ge n\)。

考虑 \(s_1+s_2>m\) 的情况，且，则一定能找到一个分界点，上下分别取到 \(s_1\) 和 \(s_2\)，此时必有 \(s_3+s_4=n\)。大概是这个图（不能同时满足 \(s_1+s_2>m\) 且 \(s_3+s_4>n\)）：

这种情况可以枚举某一条红线头的位置，注意靠上那条红线可以从左边来也可以从右边来，所以要乘 2。暴力枚举另一条红线交到的位置。剩下的四个问题独立，都是两个方向填矩阵的情况，基本组合问题。复杂度 \(O(n^3)\)

发现确定第一条红线的行之后移动列时，答案是一个固定值乘上一个前缀和的形式，可以做到均摊 \(O(1)\)。对于绿线也需要将矩阵转置一下计算。

最后剩下一种情况 \(s_1+s_2=m\) 且 \(s_3+s_4=n\)。

只能是这样的：

枚举左上角的位置计算即可，注意要算两遍，因为左上角位置既可以是横着过来的也可以是竖着过来的。

T3

有趣的数据结构题

一种暴力

维护每个数作为其中一个端点时的答案。

一个修改会对两个区间的答案造成影响。考虑如果维护这个影响。

赛时一直以为这是不可做的，实际上问题等价于维护 \(n\) 个编号连续的集合，操作是对于一段编号连续的区间都加入一个数，查询是查询全局 集合权值 + 集合中最大值 的最大值。

用线段树维护一段区间的集合，线段树上一个节点做集合操作时，这个节点代表的所有集合都具有同样的元素，因此直接取集合权值的最大值加上元素最大值即可。

解决问题的核心是将一个点的贡献/操作拆到了多个位置/多个部分，以便于对于不同的位置各自处理，这是一个非常重要的思想。

在本题中，将同一个点的贡献拆到了线段树上的多个部分，而一个线段树上的节点可以包括多个点，也便于对它们同时操作。

倍增并查集也是这个思路。倍增并查集拆分的是操作本身，将一个顺序无关操作分多步完成，多个操作的同一步可以一起做。

正解1

很神仙的一个想法是考虑按 \(k\) 将序列分块，然后块内是好做的，直接线段树维护。块间最多跨一个块。所以要统计块间的答案。

然后需要选 \(y\le x+k\) 使得 \(a_x+a_y\) 最大，然后令 \(b_i=a_{i+k}\)，变成 \(b_y+a_x\) 最大且 \(y\le x\)。

又变回了块内问题。这个问题如果在序列上是不好做的，因为额外有 \(y\ge x-k\) 的限制。但是分块统计的方式去掉了这个限制。

开一棵线段树来做这个问题，每个节点维护在这个这个节点 \(a_i,b_i\) 各自的最大值和答案，修改 \(a_i,b_i\) 时在各自的位置修改并上传答案即可。

一个问题如果能够简单的分治解决，套上线段树并记录分治过程之后就可以支持修改操作。

正解2

考虑取到答案的点的性质，由于答案由两个点构成，我们枚举了任意一个点都能得到答案，所以只需要考虑较大的那个点的性质。它满足它是区间 \([i-k,i+k]\) 中的最大值，称满足这样性质的点是好点。

我们只考虑好点的答案，于是做单点修改时只会修改常数个好点的答案，也只会有常数个好点变成不好的点或者不好的点变成好点。

好点的答案容易用线段树查询，好点答案最大值容易用 set 维护，时间复杂度 \(O((n+q)\log n)\)。

线段树需要写 zkw 以卡常。