幻影彭的彩虹

记录青春的扇区

0%

发表于 更新于

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)=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)$ 了。

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

发表于 更新于

image-20230227120527804

从 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 模型能够像人类一样同用户正常聊天，同时可以根据用户的请求检索并总结资料，甚至是独立解决数学问题。

image-20230227114909648

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$ 值作为结果：

image-20230227122102321

这条直线是 $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$ 作为函数的预测值，取得了很好的效果。

image-20230220103513820image-20230220104204613

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

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

High Dimensional Data

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

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

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

image-20230227122223309

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

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

Neural Network

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

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

What is Neural Network

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

image-20230214074656806

很像神经细胞的结构，对吧？其中 $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)$。很有意思的一件事情是这个函数是研究生物的神经元所发现的一个函数。

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

image-20230214075451013

神经网络是一层一层的，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)$ 为非线性函数）。

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

image-20230225195453688

以上图举例，在 $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)$ 对应的点上放了一个小球，向各个维度偏导的反方向移动就相当于在重力作用下自由滚动，最后一定会滚动到一个极小值点

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

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

0_zkbAm8i1k3tajJfE.png

图示优化 $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

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

image-20230301213732467image-20230301213750475

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

image-20230214094425105image-20230214094314285、

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

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

image-20230227155518243image-20230227155747814

左图为微软小冰的回答，右图为 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 具有极其强大的数据分析能力和总结，在合适的引导下，它可以从海量的互联网数据分析出使用者希望得到的部分，也对个人隐私带来了比较大的风险。

image-20230219120706043

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

Responsibility

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

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

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

Where to Go

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

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

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

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

image-20230226001326927

图示能够形式化解决某些数学问题的人工智能的输出，这是 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。

发表于

Web

Basic Auth

Basic Auth 是一种在头部提供验证账户和密码的方式，具体的，需要在 headers 参数中加入 Authorization 字端，其值为 [验证方式] [Base64 编码的账号和密码]。

参考

部分验证会忽略 Base64 的 =，所以爆破前先检查真实方式是否有 =。

数据泄露

通过爆破网站根目录下可能的备份文件获取网站文件目录结构和源码

通过访问 {源代码名}.bak 获取网页源码。

当开发人员在线上环境中使用 vim 编辑器，在使用过程中会留下 vim 编辑器缓存，当vim异常退出时，缓存会一直留在服务器上，引起网站源码泄露。

发表于 更新于

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 处有取值。

推一下公式：

如何求 $h$ ？

简单做一下代换：

考虑 $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$）：

image-20230201204107871

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

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

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

只能是这样的：

image-20230201204943731

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

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 以卡常。

发表于 更新于

题解合集1

懒得分开写咕咕咕

ARC153D

考虑 A 比较小的时候应该怎么做，记 $dp[i][a]$ 表示考虑低 $i$ 位，填的数字是 $a$，低 $i$ 位的贡献。

转移枚举下一位填什么，计算答案的方式是统计当前位上每个数字各有多少个。因为有进位所以这还比较麻烦

如果从小到大枚举 $a$，那么进位的计算是容易的，维护一个 $cnt$ 数组即可，按低 $i$ 位排序后双指针即可。

我们可以以 $O(A)$ 的复杂度计算答案。

事实上我们发现我们并不需要记录所有的 $a$，对于进位状况相同的 $a$，我们只需要它的最小值，而进位状况是 $O(2\times10^5)$ 级别的，改变状态，记 $dp[i][j]$ 表示考虑低 $i$ 位，一共有 $j$ 个数进位，只考虑低 $i$ 位时答案的最小值。

显然只会是低 $i$ 位最小的 $j$ 个数进位，答案计算式类似的。

这道题的优化本质上是分析了转移所需信息，利用问题的最优子结构性质，构造出了更加精简的状态。

ARC154D

$1$ 是比较特殊的数，如果找到了 $1$，设它的位置为 $v$，我们就可以在 $O(n\log n)$ 的时间内对其它数排好序，具体的，考虑构造一个下标序列 $a$，使得 $p_{a_i}=i$，以插入的方式来构造。二分下一个元素 $x$ 插入的位置 $i$，询问 $(v,a_i,x)$，如果答案为 Yes，那么 $x$ 应该插入在 $a_i$ 左边，否则为右边。

怎么找 $1$，对于 $1$，询问 自身+自身>其它数 都是不成立的，有一个比较容易的 $n^2$ 方式。考虑到对于 $[1,n]$ 中的任意一个数，有一半的数在询问 自身+自身>某个其它的数 的结果都是 Yes，因此可以排除一半的数，且留下来的数仍然是 $[k,n]$ 的形式，注意那个其它的数需要拿出来。做 $\log n$ 次拿出 $\log n$ 个数，以 $\log^2n$ 的复杂度检查剩下的数即可，总复杂度 $O(n\log n + n +\log^2 n)$

P5156

考虑一个逆序对，它会消失当且仅当某个端点被选择，所以排好序的必要条件是对于所有的逆序对，至少需要选择两个端点中的一个，这个条件也是充分的，因为只要存在逆序对就会被交换。

一种思路是设 $dp[i][j]$ 表示考虑前 $i$ 个元素，没有被选择的最大的元素是 $j$，且前 $i$ 个元素均合法的最小子集大小。考虑转移，一个元素 $a_i$ 选当然没有问题，不选当且仅当 $a_i>j$，否则存在一个两端都没被选的逆序对。

然后把转移图画出来发现不选的元素就是个 LIS，实际上想的时候还想了线段树去优化原式的转移emmm。

从子集的补集逆向考虑，容易发现它们之间不存在逆序对，因此子集的补集是单调的。

因此问题变成了求第字典序 $K$ 大的 LIS，很简单了。

P4187

考虑一种结果能被构造的充要条件——存在一段长度为 $k$ 的颜色相同子段。

必要性显然，充分性考虑用构造法证明，具体的，记 $a_i$ 表示 $i$ 的颜色，颜色相同的子段为 $[l,l+k)$。记 $P(c,l)$ 表示用 $c$ 颜色涂区间 $[l,l+k)$。依次进行如下操作： $P(a_1,1),P(a_2,2)\cdots P(l-1,a_{l-1}),P(n-k+1,a_n),P(n-k,a_{n-1})\cdots P(l+1,a_{l+k}),P(l,a_{l})$。

枚举第一个长度为 $k$ 的区间的左端点 $i$，记 $[1,i]$ 不出现连续长度为 $k$ 的子串，且最后一个位置不能和下一个位置相同的涂色方案数为 $g_i$

则总方案数为 $\sum\limits_{i=k}^nm^{n-k+1}g_{i-1}$

考虑 $g_i$ 的转移，不妨枚举最后一个位置的连续长度，得到 $g_i=(m-1)\sum\limits_{j=\max(0,i-k+1)}g_j$。

简单前缀和。

为什么是 $m-1$：钦定了最后一个位置不能和下一个位置相同。

另一种思考方式是考虑统计不合法的方案总数，答案就是 $m^n-f_i$。其中 $f_i$ 表示长度为 $i$ 的段，不出现连续长度为 $k$ 的子串的方案数，对于 $i<k,f_i=m^i$，否则转移和 $g$ 相同。

P7152

考虑对生成后的串 DP，设 $dp[i][c]$ 表示考虑到生成后的串的前 $i$ 个，在 $i$ 处和 $i+1$ 处被分开了，$i$ 所属的段开头(原串结尾)为 $c$ 的方案总数。

以下的串无特别说明均指被生成的串，也就是输入的那个串。

$dp[i]$ 的转移枚举起始位置 $j$ 以及对应的 $j$ 所属的段的开头字符 $c_1$，以及 $j+1,i$ 位置的取值 $c_2,c_3$，转移的要求是 $c_1=c_3$，$dp[i]$ 的第二维下标是 $c_2$，转移的额外系数也是容易计算的，不妨设它为 $w(j+1,i,c_2,c_3)$，一次转移就是 $dp[j][c_1]\times w(j+1,i,c_2,c_3)$，由于 $c_1,c_2,c_3$ 的取值都是常数种，我们干脆将它们视作一个参数 $c$，得到转移结果为 $b(j,i,c)$。

因为 $\sum\limits_j b(j,i,c)$ 对 $i$ 有比较好的转移性质，所以考虑维护所有 $c$ 的 $B_c(i)=\sum\limits_{j} b(j,i,c)$

不难发现 $b(j,i+1,c)=\sum\limits_{c_0} k_{c_0}b(j,i,c_0)$，将这个转移带进 $B_c(i)$ 里去，得到 $B_c(i+1)=\sum\limits_{c_0}k_{c_0}B_{c_0}(i)$。

能够计算 $B_c(i)$ 了，那么 $dp[i]$ 的计算也就容易了，注意对于 $B_c(i+1)$ 需要补上 $dp[i]$ 的贡献。

另一种思考方式是套路的考虑将下一个字符并入上一段或者新开一段，复杂度一样的，其实本质也是一样的。

P6142

最小值最大二分，然后一棵子树，传上去的长度自然越大越好，设 $dp_u$ 表示 $u$ 子树满足 $k$ 限制的前提下传上去的最大的数是多少，然后问题变成了对于若干个数，需要选一个或两个数配对，满足和不小于 $k$，且剩下的最大（不剩下就是 $0$）。

讨论两种情况

  • 不剩下
  • 剩下一个

显然剩下的这个数的大小有单调性可以二分，变成不剩下的情况，现在考虑怎么 check 不剩下的情况，偶数个直接最大最小，次大次小配对最优，奇数个必须先拿一个最小的不小于 $k$ 的，再如上配对。

复杂度 $O(n\log^2n)$。

P8194

发现没有 $5$ 的情况是好做的，设 $dp[i]$ 表示考虑前 $i$ 个数字的答案，当某两个可以一起按时 $dp[i]=dp[i-1]+dp[i-2]$，否则 $dp[i]=dp[i-1]$。

对于可以一起按的情况，分按和不按两种情况，不按的方案数是 $dp[i-1]$，按的方案数是 $dp[i-2]*2$，但是由于如果是顺序的，按的情况和不按的情况恰好有 $dp[i-2]$ 中是冲突的（按也能取到这种方案，不按也可以）。减掉即可。

考虑存在同时按四个的情况，这是一件很麻烦的事情，要容斥掉按四个和不按的冲突非常的困难。

不会了，换个角度思考。

考虑判定问题，即给定 $T$ 判断是否能生成 $S$，记 $ok[i]$ 表示只考虑前 $i$ 位能否生成，转移可以从 $i-1,i-2,i-4$ 转移过来。

考虑对判定过程 dp，记录前 $3$ 个位置的具体值，枚举下一个位置的具体值尝试转移，发现还需要记录前 $4$ 个位置判定 dp 的值，发现这样的 dp 恰好是不重不漏的，因为状态中三个具体值不同的显然本质不同，而 dp 值不同的显然也本质不同，所以同一阶段不同状态不重不漏，因此整个 dp 不重不漏。

总复杂度是 $O(n\times9^4\times2^4)$，跑不动，考虑常数优化。

记录三个位置的具体值很浪费，实际上大部分组合都用不到。

如果四个位置 dp 值全是 $0$ 这个状态直接扔掉。如果当最靠前的一个位置的 dp 值为 $0$，那么最后一个数是没有用的，可以压进一个状态里。如果记录的最后三个数不是接下来四个数排列，那么可以认为最后一个位置的 dp 值为 $0$，所以按最后一个位置 dp 值分类，我们的状态数变为了 $8\times 24+8\times 99$。同理对倒数第二个位置的 dp 值再分类讨论可以进一步压缩状态，状态数应该是可以压缩进 $200$ 以内的。

Tricks

  • 对于部分序列计数问题，可以考虑对判定过程动态规划，由于转移所需的序列值不同或者判定的动态规划值不同的状态时本质不同的，所以这样的动态规划是不重不漏的。
  • 上述动态规划的优化可以通过减小状态空间完成，主要方式是分析判定问题本身的性质以排除不可能对答案产生贡献的状态。

P4649

首先有一个很重要的观察，覆盖奇数条树边的非树边一定要选。

对于覆盖偶数条树边的，如果任意两条非树边覆盖的边集有交，那么一定可以构造出一种合法的路径（参考欧拉子图计数问题）。

因此问题变成选树上若干条无交的路径使得权值和最大。考虑动态规划。

设 $dp[u]$ 表示只考虑 $u$ 的子树里的路径，$u$ 子树内能选出的权值最大值，发现转移是不好做的，于是多记一维 $dp[u][k]$ 表示考虑 $u$ 子树，$u$ 连出了编号为 $k$ 的路径的权值最大值，先不计算 $k$ 的贡献，并要求 $k$ 的一个端点一定在 $u$ 子树内。

转移的时候就是儿子间两两配对，如果知道了儿子配对的方式，那么我们只需要贪心的让每一个配对取最大值转移，当然儿子也可以不配对或者和父亲配对，我们将不配归类到和父亲配对。

发现儿子配对的方式可以直接枚举，计算答案时需要一个 $mp[v_1][v_2]$ 表示 $v_1,v_2$ 儿子配对的最大值，可以枚举 lca 挂在这个点上的每条边统计。

实际上 dfs 枚举配对方式不是必要的，可以状压 dp，更好写。

教训

  • vector 用 lower_bound 删点的时候要先排好序。
  • dfs 向后枚举配对的循环里不要忘记判掉已经配好对的。

P8290

极差问题考虑枚举一下最大值位置，然后发现答案是关于最大值 $x$ 的一个 $n$ 次多项式。但是需要去重，很麻烦。

对于这种需要满足至少一个取到边界的问题，或者说与最值有关的计数问题，可以考虑容斥，用不限制取到闭区间的方案数，减去一定不满足的方案数——取到开区间的方案数，得到一定取到闭区间的方案数。

或者说正难则反，考虑一定限制下总方案减去不合法方案数。

P4233

竞赛图有一个重要结论：缩点后一定是一条链状的 DAG，每个点向后面所有点有连边。

考虑到求总的哈密顿回路是容易的：枚举一条回路，其它边任意定向，$(n-1)!2^{\frac{n(n-1)-n}{2}}$。我们考虑求出存在哈密顿回路的竞赛图个数。

由以上结论知竞赛图有哈密顿回路的必要条件是必须整体为一个强连通分量，这个条件也是充分的。

归纳的设 $k\le n-1$ 前结论成立，考虑随便从强连通分量里拿一个点出来，删掉其所有边，剩下的一定还是竞赛图——缩点后是一个链状 DAG，然后它到拓扑序最小的点一定有一条边，拓扑序最大的点到它一定有一条边，然后从这个点开始，走拓扑序最小的点。在每个 SCC 内部找到对应的哈密顿回路并将最后一步连向下一个 SCC，最后从拓扑序最大的 SCC 回来即可，因为走到下一步的过程中是可以任意选择下个 SCC 的起点的，所以确定每个 SCC 内部的哈密顿回路之后需要选一个能够回去的位置开始。

直接算强连通的竞赛图数量不好算，考虑容斥，总的图有 $2^{\frac{n(n-1)}{2}}$ 个，对于不联通的图，枚举拓扑序最小的 SCC 大小，不相关的边可以任意定向，从最小的 SCC 连向其它点的边必须同向，设 $f_n$ 表示 $n$ 阶竞赛图强连通的方案数，有：

设 $g_n=2^{\frac{n(n-1)}{2}}$，改写为：

可以分治 NTT 了，但是继续考虑其指数生成函数的形式幂级数 $F,G$。

然后移项解方程，$F(x)G(x)=2G(x)-1\iff F(x)=\dfrac{-1}{G(x)}+2$。

多项式求逆即可。

对于固定 $n$ 的情况，其实归纳的考虑较小的 case 也是一种策略。

CF1542E2

最开始考虑把两个条件都写出来看能不能容斥，然后发现不行。

考虑枚举第一个条件在哪里满足，也就是两个排列第一次不同的位置，对于逆序对，前面相同的部分逆序对不管，前后跨越的部分也可以不管。然后可以将后面看成一个新的排列做，第一个不同的位置和后面的逆序对个数有差异！具体的，如果 $p$ 为 $x_p$，$q$ 为 $x_q$，那么在该位置 $p$ 比 $q$ 少 $x_q-x_p$ 个逆序对。

后面仍然可以看成一个排列，然后枚举一下 $p$ 比 $q$ 少的数量 $d$，接下来问题就变成了求两个排列逆序对相差多于 $d$ 的方案数。再枚举一下较多那个排列具体有多少个逆序对，另一边是前缀和，基本问题就变成了求 $n$ 阶排列有 $x$ 个逆序对的方案数。

这个基本问题可以动态规划，按位置做不好做，所以按值从小到大做，具体的，设 $dp_{n,x}$ 表示 $n$ 阶排列有 $x$ 的逆序对的方案数，考虑插入下一个 $n+1$，答案还是前缀和。

基本问题在 $O(n^3)$ 内解决了，但是刚刚的过程是 $O(n\times n\times n^2)=O(n^4)$ 的，考虑优化，记 $f_{n,i}$ 表示 $n$ 阶排列 $i$ 个逆序对的方案数，$g$ 为其前缀和，先写式子：

后面那个 $\sum$ 也是可以前缀和的。

变成 $O(n^3)$。

CF798D

先考虑了每个数和中位数、平均数的大小关系来决定是否选择。然后想能不能构造 $c=a+b$ 在 $c$ 上先贪心选择然后再调整让不满足条件的那个数组满足条件。都失败了。

两个数组都是无序的不好考虑，将 $a$ 降序排列。考虑钦定 $b$ 满足条件并尽可能使 $a$ 满足条件。如果 $n$ 为奇数，我们可以选择 $a_1$，然后将后面的两两分组。每一组选择 $b$ 较大的那一个，这样 $b$ 一定满足条件。然后又因为我们选了 $a_1$，$a_1$ 和第一组配对，第一组的 $a$ 和第二组的 $a$ 配对，然后 $a$ 也满足条件。

偶数同理。

构造完了，这种贪心按对决策的思路很有学习价值，题目中的选一半也提示了这种方式。

ARC156C

给树上每个点一个权值，构造一种方案使得树上所有路径的权值和编号构成序列的 LCS 的最大值最小。

首先放到链上去做，发现长度最大为 $1$，并且方案固定——逆序，猜想总能构造出长度为 $1$ 的解。应该需要利用逆序的性质。

想的是随便定一个根从下往上构造，叶子就优先连上去，每个点只会往上传 1-2 个，然后 $n$ 为奇数的时候在根上遇到了麻烦（这个麻烦是因为没有注意到两个互换的点即使经过了一个不动点贡献也不会增加出现的。）

然后发现类似的思路都处理不了拉一条长链的情况。

于是考虑找一些点集互换，拉出一半的点来，两边各自按深度排序，对应互换填进去，这样对于两边的任意一条路径经过的一定是倒序的另一边，最大长度为 $1$。但是注意到有可能从一个点集经过另一个点集再回到第一个点集，这样就不行了，所以要找到重心按子树大小排序后划分，这样能保证不存在上述情况。

其实有更简单的方式，每次选两个叶子连上去，一直这么做直到只剩下一个，每次选完叶子后因为如果这一对点要算进 LCS 里面就必须选了一个之后马上跳到另一个，中间路径的所有贡献都将被忽略，如果剩余部分同样这么构造就没问题。

这种方式是一种典型的归纳思考的方式，需要学习。

最开始思路出现问题的一个重要原因还是简单的认为只要一条路径覆盖了被交换的点，这一对点就会贡献，实际上还有一个顺序问题。

有时候重新审视题目是很有必要的。

ARC156D

最开始想到逐位确定答案，然后发现只能确定最末位，对于高位由于各个位数复杂的贡献不好算。

然后发现这个是异或问题，而且等价的方案是可重排列，大概率是偶数，于是想到分析有贡献的方案。

运用卢卡斯定理可以知道，一个方案有贡献当且仅当可以被划分成 $k$ 的子集，而且不能有交，也就是对于 $k$ 中的每一个二进制位，都只能有一个数选择它。问题变成了求 $\sum a_{p_i}2^{k_i}$ 的，注意到 $a$ 的值域是 $1000$，也就是说如果过了 $11$ 个二进制位之后前面的数就没用了，所以考虑设 $dp_{i,k}$ 表示考虑到二进制下第 $i$ 位，这一位上的值为 $k$ 的方案数，转移枚举下一个二进制位选哪一个，并和前一位的进位加起来。答案的统计可以在移动最低位时进行，最开始我直接用此时的 dp 出来的方案数作为贡献计算，然后错了。看题解后才注意到此时的 dp 值并不是实际上这一位为这个值的方案数， 还需要考虑后面的选择对此时方案数的贡献。于是当 $k$ 接下来的二进制位还有 $1$ 时，只有在 $n$ 为奇数时才贡献，如果 $k$ 的所有二进制位都被考虑完了，后面才不会有更多的选择贡献到当前的方案数。

教训

  • 计数类的问题，如果要在动态规划的过程中计算贡献，一定要考虑之后的选择对当前方案数的影响——当前计算出的 dp 值并不是最终的方案数。

ARC157C

值的平方，拆成有序对的贡献，考虑一段 YY 能和前面的哪些配对，对于靠前的那个 Y 统计，实际上需要算的是从 $(1,1)$ 到该位置的所有路径中有几个 YY，很简单的动态规划。

ARC157D

由于划分是一行一列的划分，又因为每一个格子都是相等的，所以每一列也是相等的。

确定了一列具体有几个之后，每一列划分的位置都在一段区间摇摆且不交，而且对于任何一种划分位置选择，对行的划分都是等价的，于是枚举合法的一列的个数，求出列划分方案数。然后再求对应的行划分方案数乘起来就行。行划分方案在确定了列划分之后，每个可能的划分位置所在区域都不交。

算最边界的时候不能浮动，只能取最外面，不能乘上其贡献。

HDU6801

设 $q=1-p$。

最开始想枚举圈数，算第 $c$ 个在第 $t$ 圈第 $i$ 个被删的概率，然后想直接算一个组合数的概率。但是不知道具体经过了多少次选择，而且组合数和 $t$ 有关很丑陋，于是没考虑。

实际上，这类题有一个 Trick，可以不真正的删掉一个点，而是给它打标记，最后算有多少个打了标记，于是算概率就可以不用组合数，可以考虑每一个点，它被打标记的概率是 $1-q^t$ 或者 $1-q^{t+1}$，然后就是选 $i-1$ 个点被打标记然后钦定第 $c$ 个在第 $t$ 圈第一次打标记的概率。

或者说，我们不去关心每一个具体在 $t$ 圈中的哪一圈被删除，只关心 $t$ 圈后它是否存在，存在的概率是 $q^t$，补集就是不存在的情况。

于是记 $a_i$ 表示第 $c$ 个在第 $i$ 次删除操作中被删除，$t$ 从 $1$ 开始不好，让它从 $0$ 开始：

考虑 $a$ 的生成函数 $A(x)$：

那个 $1-q^t$ 和 $1-q^{t+1}$ 如果暴力枚举二项式次数拆开，在第一次拆分的时候是合并不了的，会给后面的计算带来很大麻烦，可以把 $q^t$ 提出来将二项式稍微简化一些。

记一个 $f_k=\frac{1}{1-q^{k+1}}\sum\limits_{i=0}^{k}\binom{c-1}{i}\binom{n-c}{k-i}q^i$，$f_k$ 可以卷：

$f=a * b,a_i=\binom{c-1}{i}q^i,b_i=\binom{n-c}{k-i}$，注意两项各自的边界。

再来推：

然后也可以卷了。

另一种思考方式是动态规划，设 $f(n,i,c)$ 表示第 $c$ 个在还剩 $n$ 个情况下被第 $i$ 次删掉的概率，转移可以枚举下一次删掉的是哪一个：

由于是要对每个 $i$ 算，所以状态数是 $O(n^3)$ 的，跑不掉，会死掉的。

考虑先绕到 $c=1$ 然后再一圈一圈弄，记 $f(n,i)$ 表示还剩 $n$ 个，第一个在第 $i$ 次被删掉的概率，先考虑怎么用 $f(n,i)$ 算答案 $a_i$。

然后可以卷，于是问题变成了算 $f(n-j,i-j)$。太麻烦了，先咕咕咕了。

P5401

减法卷积

解决形如 $f_i=\sum\limits_{j=i}a_jb_{j-i}$ 的卷积。

教训

  • 推式子的时候不要漏了 $-1$ 项和组合数项。
  • 算卷积的时候，由于习惯用 vector 封装，复用 vector 的时候一定要把后面的无用项设成 $0$，乘法返回的 vector 后面是有无用项的，原来用过的因子项数组复用时也要小心。
  • multi 函数里面记得要 resize。

发表于 更新于

A

简单，不过我蠢

偶数构造显然。

奇数不存在合法方案，不用枚举。

B

简单贪心。

C

每个 $x_i$ 的取值最多有两个，因为如果不取到边界，那么向左或者向右调整一定会变得更优。

直接做一遍动态规划即可。

D

简单图论

E

考虑能构造的一个必要条件，异或值本身需要满足且最高位的个数足够。

注意到对于连续的一段 $[1,n]$，高一位的 $1$ 的个数不会多于低一位的 $1$ 的个数，证明考虑最高位 ($n$) 和次高位 ($n-1$)，次高位在最高位出现之前就取到了 $2^{n-1}$，最高位为 $1$ 时，最多有 $2^{n-1}$ 个数取不到次高位。

对于最高位个数足够的情况，取拥有最高位的 $k$ 个数，以及 $a_i\oplus x$，由于异或的性质，被取到的剩下的数一定互不相同，且这样构造取到了理论最大值，将剩下的数随便塞进一组里，由于异或值本身需要满足的必要条件，一定不影响异或结果。

注意特判 $x\oplus0$ 的情况。

F

定义排列乘法为 $a=b\cdot c,a_i=b_{c_i}$。

给定一个排列 $p$ ，问是否存在一个排列 $q$ 满足 $q^{2^k}=p$，如果存在，构造一种循环个数最小的 $q$，否则报告无解。

对于 $q$ 的每个循环我们考虑乘方之后会怎样。

将一个循环 $w$ 写出，例如 $1,2,3,4$，自乘一遍之后变成 $1,3;2,4$，再自乘一遍（乘最开始的排列）变为 $1,4,3,2$。如果以图的形式表现，$w^p$ 表现为将第 $i$ 个点的边连到第 $i+p$ 个点，注意到如果 $\gcd(p,len)\ne 1$，那么循环个数就会减小。

考虑变换后的排列 $p$，求出其所有循环，对于奇数长度的循环，可以将它们以 $2^i$ 的形式合并起来，这样得到的循环个数是最小的，注意 $i>k$ 的情况。

对于偶数长度的循环，如果个数不足 $2^k$，那么它们就无法被拼接起来，否则也只能以 $2^k$ 为单位拼接起来。

考虑将若干个长度相同的循环还原为 $q$ 中的循环，我们知道的是，对于 $q$ 中的原循环，将边连向 $2^k\bmod len$ 之后的点得到了若干个长度相同的循环，那么对于这些长度相同的循环，我们在每个循环中先取一个，然后接下来才需要取同一循环的元素。

设 $p$ 中一个循环的长度为 $m$，总共 $n$ 个循环，一种简单的构造方式令 $p$ 中第 $i$ 个循环的第 $j$ 个元素，占用第 $((\frac{jk}{n})\bmod m)*n+i$ 个位置，那么显然在原来 $q$ 的循环中，$p$ 中每一个循环的元素到下一个元素的距离为 $k$。

G

考虑暴力怎么做，拿一个可重集维护所有颜色的答案，修改一个点时，暴力修改和这个点连接的所有颜色的，将它们从集合中删除或者加入。

这样做一次操作复杂度和度数有关，无法通过本题。

将问题进一步抽象后发现它并不是一个好做的问题——和 CSP-S2022T3 有点类似，这种一对多的指定整体修改问题并不好做。考虑利用问题抽象前的性质——树上问题。

修改一个点时受到影响的颜色可以分为路径 lca 是它和不是它，后者只有一种，可以暴力修改，对于前者可以对每一个点用 priority_queue 维护路径 lca 为它的最大权值，这样就能做到 $O(n\log n)$。

细节有点多：

  • 从树中提出链的时候，判断度数的条件应该是 (fa==0)+cnt>2 则不为链，(fa==0)+cnt==1 则为端点
  • 不合法的颜色不应该被统计进它 lca 的 priority_queue 中。
  • 如果一个 lca 不合法，那么它的权值不在总的 priority_queue 中，对它某一个儿子修改时自然不应该修改总的优先队列。

发表于

A

简单

B

简单

C

每次选一对，最大的放后面，最小的放前面，问排序好一个排列的最小次数。

考虑没有动过的那些数，它们一定是一个上升子序列，且满足 $a_{k_i}=a_{k_{i-1}}+1$。

对于其它动过的那 $c$ 个数，容易在 $\lceil\frac{c}{2}\rceil$ 次之内将它们排好序

操作不可逆的最小次数排序问题，可以考虑没有操作过的那些数

D

定义两个排列的乘法（复合）为 $c=a\cdot b$，$c_i=b_{a_i}$，给定 $n$ 个长度为 $m$ 的排列，对于每个排列 $p_i$ 需要找出一个排列 $p_j$，使得 $p_i \cdot p_j$ 的美丽度最大，定义一个排列 $q$ 的美丽度为一个最长的前缀的长度，满足 $q_i=i$。

考虑一个已知排列 $a$ 复合上另一个排列 $b$ 后，美丽度为 $k$ 时对 $b$ 的要求，容易发现要求为 $\forall i\in[1,k],b_{a_i}=i$。就是对于 $b$ 的一些位置，要求固定为某些数。

这并不是一个很好 check 的条件，注意到要求的数为 $[1,k]$，所有考虑排列的逆排列，要求变成了对于前 $i$ 个位置，满足 $b’_i=a_i$，这是一个容易检查的条件。

参考 排列变换总结 中的定义。

E

题意转化为对每个 $m=m_1\cdot m_2$ 的约数 $d$，求出其最大的不超过 $n$ 的约数。

约数的约数，级别还是挺大的，对于 $10^{18}$ 的数，可能达到了 $10^8$ 级别，不能暴力枚举，$10^{18}$ 内的最大约数个数约为 $10^5$ 个。

考虑一个约数的最大的不超过 $n$ 的约数，它显然也是 $m$ 的一个约数，考虑以一种类似动态规划的方式递推，枚举一个约数的所有质因数，从它们各自的最大约数转移过来，显然这是对的。

F

发表于 更新于

常见排列变换

循环

我习惯将循环的顺序定义为正向，即循环 $1,2,3,4$ 对应的排列为 $2,3,4,1$。更加数学化的表达，$p$ 的循环 $a_1,a_2\cdots a_k$ 表示 $p_{a_1}=a_2,p_{a_2}=a_3\cdots p_{a_k}=a_1$。

求逆

定义一个排列 $p$ 的逆排列 $q$ 满足 $p_{q_i}=i$，通俗的讲，$q_i$ 表示 $p$ 中元素 $i$ 的位置，$q$ 一般记作 $p’$ 或 $p^{-1}$。

有性质 $p’’=p$。证明是简单的，$p_{p’_i}=i,p’_{p’’_i}=i$，所以 $p_{p’_{p’’_i}}=p’’_i$，又有 $p’_{p’’_i}=i$，所以 $p_i=p’’_i$。

在排列循环中，求逆的等价于将边反向，以上性质也就不证自明了。

置换和乘法

定义两个排列的乘法 $c=a\cdot b,c_i=a_{b_i}$。

以置换的方式定义

$a\cdot b$ 等于 $a$ 左乘上置换 $b$。

自乘或次幂

如果是自乘，那么等价于循环的边移动若干次，$b$ 次幂就是将 $a_i$ 的边指向 $a_{((i+b-1)\bmod k) + 1}$

非自乘

对于非自乘，我们研究它的运算律。

  • 没有交换律

  • 存在单位元 $e$ 满足 $a\cdot e=e\cdot a=a$。

  • 存在结合律

    • 置换的乘法运算存在结合律，被定义为左乘的排列乘法自然具有结合律。

    • $a\cdot b\cdot c=c\circ(b\circ a)=(c\circ b)\circ a=a\cdot (b\cdot c)$

    • 置换乘法的结合律描述为 $a\circ b\circ c=a\circ(b\circ c)$，证明是容易的，此处不再赘述。

  • 存在逆元

    • 一个置换 $\begin{pmatrix}1,2\cdots n\\a_1,a_2\cdots a_n\end{pmatrix}$ 的逆元显然为 $\begin{pmatrix}a_1,a_2\cdots a_n\\1,2\cdots n\end{pmatrix}$，也可以写成 $\begin{pmatrix}1,2\cdots n\\a’_1,a’_2\cdots a’_n\end{pmatrix}$
    • 对于 $a$ 置换的逆元 $a’$，容易发现 $a’’=a$，因此 $a’\circ a’’=a’\circ a=e$
    • 因此 $a\cdot b\cdot b^{-1}=a=b^{-1}\circ(b\circ a)=e\circ a=e\cdot a=a$

​