幻影彭的彩虹

先验概率 VS 后验概率

定义

• 先验概率是根据主观经验，在没有任何实验的情况下对某件事情发生概率的预测。

• 后验概率是根据某些已知证据，去估计的事情发生的概率。 \[ P(H|E) = \dfrac{P(E|H)*P(H)}{P(E)} \] 该式子中，每项含义如下：

  • \(P(H|E)\)：在证据 \(E\) 成立的前提下，假设 \(H\) 成立的概率。
  • \(P(E|H)\)：在假设 \(H\) 成立的前提下，证据 \(E\) 被观测的概率。
  • \(P(E)\)：证据 \(E\) 成立的先验概率。
  • \(P(H)\)：假设 \(H\) 成立的先验概率。

朱世衡之问

有关朱世衡提出的硬币之问，不妨设 \(E\) 表示抛 \(100\) 次硬币 \(50\) 次正面朝上，\(H\) 表示 \(p=0.9\)，也就是正面朝上的概率为 \(90\%\)。那么：

• 可以计算出 \(P(E|H)\le \epsilon\)，也就是如果 \(H\) 成立，那么观测到 \(E\) 的概率会很小。

• 不能说：因为 \(P(E|H)\le \epsilon\)，所以 \(P(H|E)\) 很小。

• \(P(E)=\int^1_0{P(p=x)\cdot P(E|p=x) dx}\)，显然 \(P(p=x)\) 是个先验概率，是确定不了的，所以 \(P(E)\) 没法计算，同理 \(P(H)\) 也没法计算，故 \(P(H|E)\) 计算不了。

最大似然

一般求解方式

• 考虑后验概率函数相对简单且为凸函数，对后验概率每个参数求偏导即可解出最大似然。
• 对后验概率函数使用梯度下降，求解极大似然。

EM 算法

算法用途

EM 算法主要用于近似求解一些最大似然问题。

算法流程

1. 初始化模型参数 \(\theta\)。
2. 对 \(\theta\) 进行迭代，优化 \(Q(\theta | \theta^{(t)}) = \mathbb{E}_{Z|Y,\theta^{(t)}} \left[ \log P(Y,Z|\theta) \right]\)。
   • 根据 \(\theta^{(t)}\) 计算 \(Z\) 不同取值的后验概率密度函数 \(F = P(Z=x|\theta^{(t)})\)。
   • 根据 \(F, \theta^{(t)}\) 求解上式的最大似然。

算法举例

有三个硬币 \(A,B,C\)，正面朝上的概率为 \(\theta_A,\theta_B, \pi\)，每次实验先抛硬币 \(C\)，如果 \(C\) 正面朝上，则使用 \(A\)，否则使用 \(B\)，一次实验抛完 \(C\) 后抛 \(A\) 或 \(B\) 五次，记录为：

1
2
3
4
5
6
7
8
9

实验一：2 正 3 反

实验二：4 正 1 反

实验三：1 正 4 反

实验四：3 正 2 反

实验五：4 正 1 反

根据实验结果给出一个最大似然参数估计 \(\theta = (\theta_A, \theta_B, \pi)\)。

E 步骤

计算每个实验由 \(A\) 或 \(B\) 生成的后验概率：
\[ \gamma_j(A) = \frac{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j}}{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j} + (1-\pi) \cdot \theta_B^{n_j}(1-\theta_B)^{m_j}} \]

M 步骤

迭代更新： \[ \pi' = \frac{\sum_{j=1}^5 \gamma_j(A)}{5} \]

\[ \theta_A' = \frac{\sum_{j=1}^5 \gamma_j(A) \cdot n_j}{\sum_{j=1}^5 \gamma_j(A) \cdot 5}, \quad \theta_B' = \frac{\sum_{j=1}^5 \gamma_j(B) \cdot n_j}{\sum_{j=1}^5 \gamma_j(B) \cdot 5} \]

迭代

设置一个收敛阈值，似然估计变化小于阈值时令其停止。

EM 原理证明

首先对似然函数取对数，记： \[ L(\theta) = \log(P(Y|\theta))=\log{\sum\limits_{z}P(YZ|\theta)}=\log(\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)) \] 考虑： \[ \begin{align} L(\theta) - L(\theta^{(i)})&= \log\big({\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)}\big) \\ &=\log\big({\sum\limits_{z}P(Z|Y, \theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}}\big) - \log(P(Y|\theta^{(i)})) \end{align} \] 由 \(\text{Jensen}\) 不等式，得 \[ \begin{align} \text{上式} &\ge \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}} - \log(P|\theta^{(i)})\\ &= \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(|\theta^{(i)})}}) \end{align} \] 令： \[ \begin{align} B(\theta, \theta^{(i)})&= L(\theta) + P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(Y|\theta^{(i)})}}\\ &=L(\theta)+P(Z|Y,\theta^{(i)})\log{\frac{P(YZ|\theta)}{P(YZ|\theta^{(i)})}} \end{align} \] 第二行来自贝叶斯公式。

则有 \(L(\theta)\ge B(\theta, \theta^{(i)})\)，且 \(B(\theta,\theta)=L(\theta)\)。

所以令： \[ \theta^{(i+1)} = \mathbf{argmax}_\theta B(\theta, \theta^{(i)}) \] 则有： \[ L(\theta^{(i+1)}) \ge B(\theta^{(i+1)}, \theta^{(i)}) \ge B(\theta^{(i)},\theta^{(i)})=L(\theta^{(i)}) \] 即： \[ L(\theta^{(i+1)})\ge L(\theta^{(i)}) \]

算法分析

对比

上面的三硬币问题理论上也可以直接求解最大似然，但是列出来后是一个 PDE，一般 PDE 目前是没有闭式解，所以也只能退而求其次找近似解。

梯度下降也行，但是相比于 EM，梯度下降的梯度计算比较复杂，而且无法保证满足概率约束，可解释性弱，收敛不可靠等等等。

M 步骤最大似然的求解

三个变量是独立的，分别求偏导就能代出值来。

本文介绍了 Docker 的基本操作方法, 强调了一些易错点.

本文是神经网络学习笔记，主要记录了几种常用神经网络的结构和变体，以及一些训练技巧及其原理。

本文以现代计算机网络硬件为基础，介绍了现代硬件环境下应该了解的网络知识，能够为网络编程打下一个较好的基础。

一些日常可能会用得上的技术（二）

写在前面

虽然很多人能够熟练掌握一门编程语言，也能用这门编程语言方便的批处理数据，但是每次总要借助这门语言的 编译器/解释器，然后调用一些系统函数之类的，总感觉缺了点意思。

Linux/Windows 其实在 shell 中已经提供了一门完备的编程语言来直接处理文件或者数据，这相比与写一份代码来运行它要有趣很多。

你不必记下本文的所有细节，只需要知道有这些所介绍的功能即可，记忆会在你的使用过程中一步步完成，AI 能提供的信息会比本文更详尽。

一些常用命令

grep

1

grep [选项] 模式 [文件...]

• 选项
  • -i：忽略大小写。
  • -r：递归搜索子目录。
• 模式
  • 默认是标准正则。
  • 用 -F 参数禁止正则（所有正则符号被视为文本）。
  • 用 -E 支持扩展正则表达式。
• 文件
  • 用 - 表示标准输入。（第一期讲过 "一切皆文件"）
  • 支持多个文件，每个文件用空格隔开。
  • 文件名可以采用通配符语法（见附录，大部分文件名参数都可以支持通配符）。
    • 通配符语法匹配的并不是相对路径，而是对于每一层目录和文件名独立匹配，也就是说 f1/*.txt 不能匹配 f1/ 子目录下的 .txt 文件。
• Windows 平替
  • 可以去下载一个 ripgrep 加入系统路径后当平替，用法基本一致，命令改为 rg。

echo

• 用于输出字符串。

  1	echo [一个字符串]

• 常用参数

  • -e：指定转义 \ 相关的换行（\n），制表符（\t）等。
  • -E：指定不转义。

• 备注：

  • 不同操作系统的 echo 标准不一样，所以有 -e-E 这种看上去反人类的参数。
  • Windows 系统的 PowerShell 也有 echo，但是它的转义符是 "`"，系统默认发生转义操作。

cat

• 题外话

  • 见下图。

    

  • 为什么学计算机的很多人都喜欢猫~~？

• 查看文件内容

  1	cat [文件...]

  • 会输出结果到终端。

• 其它用法

  • 写入文件：

    1	cat [文件...] >> file.txt

    • >：覆盖写入。
    • >>：追加写入。

  • 文件部分可以接受命令行输入，> 或者 >> 前不填写任何参数就使用命令行输入。

  • 使用 EOF

    1	cat > file.txt << EOF

    • 接下来的输入中，输入 EOF 并回车结束输入，EOF 不会被写入。

    • 如果不使用 << EOF 也不使用管道

wc

• 统计文件字数

  1	wc [文件...]

• 常用参数

  • -l：统计行数。

• 其它

  • 可以接受命令行输入。

    1	command | wc -m

head/tail

1

head [文件名...]

• 用于显示文件的最开始/最后 10 行。
• 常用参数：
  • -n：紧接着可以指定行数。
• 其它：
  • 支持命令行输入

rm

1

rm [文件名...]

• 用于删除文件。

• 常用参数：

  • -r：用于删除目录。
  • -f：忽略警告直接强制删除。

• 某个很厉害的命令：

  1

  rm -rf /

  功能是删除本操作系统下所有文件，请不要执行或者被人忽悠执行该命令！

  数据无价，谨慎操作。

zip

1

zip [选项] [压缩文件名] [被压缩文件/被压缩目录...]

• 用于创建压缩文件。
• 常用选项：
  • -r 或 --recursive：递归地包含目录，即包括指定目录及其所有子目录。
  • -u 或 --update：更新现有的 zip 文件，添加新文件或更新已存在的文件。如果不用改参数覆盖时会提示。
  • -x 或 --exclude：后面输入一些 [被压缩文件/被压缩目录...]，排除指定的文件或目录。
  • -v 或 --verbose：详细模式，显示正在处理的文件名。
  • -q 或 --quiet：安静模式，不显示任何输出。
  • -0 到 -9：设置压缩级别，从无压缩（0）到最大压缩（9）

uzip

1

unzip [压缩文件名] [参数]

• 用于解压文件，默认解压到当前目录。

• 常用参数：

  • -d：后面接一个目录，解压到这个目录，不存在会创建。
  • -l：只查看里面的文件，不解压。

• 其它用法

  • 只解压部分文件

    1	unzip [压缩文件名] [要解压的文件在压缩文件中的路径...] [参数]

管道

• 管道的一般用法是 command1 | command2 ，功能是将 command1 的标准输出作为 command2 的标准输入运行。

• 举例：

  • 使用 sort 对文件内容排序，并用 uniq 去除重复行：

    1	sort somefile.txt | uniq

  • 使用 ls 列出目录内容，grep 过滤特定模式的文件，然后 sort 排序结果：

    1	ls -l | grep "^-" | sort

变量

声明

1

key=value

• = 的左右不能用空格。
• value 加上双引号被声明为字符串，不加声明为整形变量或者浮点变量。
• PowerShell 的声明使用 $key=value。

变量引用

1
2

${变量名}
$变量名

• 第一种方式是为了防止歧义。
• 用 \ 可以转义 $。

运算

• $((expr)) 语法：

  1	$((算术表达式))

  • 举例：

    1 2 3 4

    a=5 b=3 c=$((a + b)) echo $c # 输出 8

• 自增自减：

  1

  $((a++))

• PowerShell 特性：

  1

  $a++

  • 可以直接这样使用，但是在 echo 等命令中这样做不行。

• Shell 特性：

  1	let "new_var = var1 + var2"

  • new_var 可以是一个新变量名。

总结

• 大部分时候，常用命令的正则表达式、通配符等功能就可以完成大部分需要循环和分支的操作，用得上循环和分支的地方实际上不会很多。就算真的需要用到循环这些操作，这个时候使用 Python 等脚本语言可能会更方便了。
• 好好学习正则表达式。

附录

关于一些语法

• 可变参数列表：[文件...] 是一个可变参数列表，习惯上命令行参数用空格隔开，所以它实际上表示 [文件1] 或 [文件1] [文件2] 或 [文件1] [文件2] [文件3] 等等。

关于标准正则（BRE）

• .：匹配任意单个字符（除换行符外）。
• ^：匹配每一行的开头（不占位，第一个字符仍需要被模式匹配）。
  • 也用于脱字，放在 [] 内部的最开始表示匹配除了 [] 中表达字符之外的所有字符
• $：匹配行的结尾。
• []：匹配括号内的任意字符。
• |：逻辑或操作符。
• *：匹配前面的元素0次或多次。
• +：匹配前面的元素1次或多次。
• -：行为视上下文而定。
  • 在 [] 内它是一个特殊字符，它表示一个范围，例如[a-z] 可以匹配任何小写字母。
  • 在 [] 外是一个普通字符。
• ?：匹配前面的元素0次或1次。
• {n}：精确匹配n次。
• {n,}：至少匹配n次。
• {n,m}：至少匹配n次，但不超过m次。
• \（反斜杠）：转义特殊字符或表示特殊序列的开始。
• ()（圆括号）：将多个表达式组合成一个子表达式，用于分组和捕获。

关于拓展正则（ERE）

• \b：匹配一个单词字符和非单词字符之间的边界。
• \d：等价于[0-9]。
• \D：等价于[^0-9]。
• \s：等价于[ \t\n\r\f\v]。（空白字符）
• \S：等价于[^ \t\n\r\f\v]。（非空白字符）
• \w：等价于[a-zA-Z0-9_]。（单词字符）
• \W：等价于[^a-zA-Z0-9_]。（非单词字符）
• \n：匹配换行符。
• \t：匹配制表符。
• ?：非贪婪匹配（lazy quantifier）。

关于通配符

通配符拥有部分正则的特性，支持不如正则完整，语法有微小差异，具体细节如下：

1. *：匹配任意数量的字符（包括零个字符）。
   • 例如：*.txt 匹配所有以 .txt 结尾的文件。
2. ?：匹配任意单个字符。
   • 例如：file?.txt 匹配 file1.txt、filea.txt 等。
3. [...]：匹配括号内的任意单个字符。
   • 例如：file[123].txt 匹配 file1.txt、file2.txt 和 file3.txt。
   • 也可以使用范围：file[a-z].txt 匹配 filea.txt 到 filez.txt。
4. [!...] 或 [^...]：匹配不在括号内的任意单个字符。
   • 例如：file[!123].txt 或 file[^123].txt 匹配除了 file1.txt、file2.txt 和 file3.txt 之外的所有以 .txt 结尾的文件。
5. {...}：匹配花括号内的任意选项（选项之间用逗号分隔）。
   • 例如：file.{txt,pdf} 匹配 file.txt 和 file.pdf。
6. \：用于转义自己和以上特殊符号。

一些日常用的上的计算机技术（一）

写在前面

在 AI 背景下，很多日常处理数据的工作完全可以交给 AI 来完成，学习它们的必要性似乎已经不那么强？

在大模型时代，更重要的是了解一些技术的存在，而非具体掌握这些技术，本文旨在提出某些可能对日常工作有帮助的技术，大致给出一个框架。

最后，我想说，一个全栈工程师，需要掌握的不是整个计算机系统中所有方向的技术，而是整个计算机系统的脉络。当一个需求被提出时，他能够沿着大脑中的脉络找到所需的枝叶技术，并运用自己熟练的信息检索能力来找到它们的技术细节，并最终将这些技术组合成解决方案。

可持久化

• 其实用 "可持久化" 来形容它并不准确，这也包括把 hardcode 部分分离以便让用户不必修改源代码运行程序的相关技术。

  • 举例来说比如爬虫要爬一个网站，你有可能直接把一些参数写进代码里，例如：

    1 2 3 4 5

    URL = "www.google.com" PROXY = { http_proxy: "localhost:7890", https_proxy: "localhost:7890" }

  • 但是你某一台电脑的代理端口是 localhost:7891，所以一个方案是直接修改源代码，但是这太麻烦了，因为代码可能会比较长然后你需要翻。

  • 所以一个方案是单独把一些可能会变的配置给提出来单独写一个配置文件，然后每次运行代码的时候你输入配置文件的路径，或者仅 hardcode 配置文件路径。这样都比一个个改参数更好。

  • 配置文件可以用 .yaml 或者 .json 文件，我习惯用前者，但其实后者的适用性更广，大部分编程语言内置了处理 .json 文件的相关函数。

• yaml 使用：

  • 准备：

    1	pip install PyYaml

  • 读取：你大可直接复制下面的代码。

    1 2 3 4 5 6

    def yaml2dict(file_path, encoding='utf-8'): if check_suffix(file_path, 'yaml'): with open(file_path, 'r', encoding=encoding) as f: return yaml.safe_load(f) else: raise ValueError("file suffix name not support")

  • 写入：用 yaml.safe_dump(obj, stream)

    • obj：一个 Python 对象，一般只支持基本数据类型。
    • stream：一个可写流对象，可以用 with 操作打开。

批量发送电子邮件

• 用 email 和 smtplib 来发送，这俩是标准库，不用安装。

• 大概可以看看下面的代码：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  import smtplib from email.mime.text import MIMEText from email.mime.multipart import MIMEMultipart def send_mail(receiver, html, subject): message = MIMEMultipart("alternative") # 交替 attach 模式 message["Subject"] = subject # 邮件标题 message["From"] = SENDER # 发送者邮箱 message["To"] = receiver # 接收者邮箱 part = MIMEText(html, "html", "utf-8") # 三个参数是: html 字符串, 格式名, 编码方式 message.attach(part) # 将对应的 part 正式加入 message # SMTP服务器和端口，这是 google 邮箱的网址和端口，服务器和端口取决于发送者的邮箱。 smtp_server = "smtp.gmail.com" port = 587 try: server = smtplib.SMTP(smtp_server, port) # 建立 SMTP 连接 server.starttls() # 启用TLS安全传输模式 server.login(SENDER, PWD) # 两个参数分别为邮箱账号和密码 server.sendmail(SENDER, receiver, message.as_string()) # 发送 print("邮件发送成功") except Exception as e: print("邮件发送失败", e) finally: server.quit() # 断开服务器连接

Excel/Word 处理

Excel 处理

• 我使用的是 pandas 库。

  1 2	pip install pandas pip install openyxl

• 这样读取：

  1 2 3 4

  import pandas as pd xls = pd.ExcelFile(r"C:\Users\huany\Desktop\帆软杯\第六届帆软杯报名信息（" + group + f"） - 含准入码.xlsx") sheet_name = xls.sheet_names[0] df = pd.read_excel(xls, sheet_name=sheet_name)

• df 是转出来的 DataFrame 对象，有以下几个注意点：

  • 一个表格的第一行自动作为表头，每一列的内容作为索引指标。
  • 用 df['col_name'] 来获取一列，它是一个 iterable 对象。
  • 用 df.iterows() 来迭代每一行，得到的行是一个类 dict 对象，用表头的数据作为指标。

Word 处理

• word （.docx 文件）是基于 xml 的文档。
• .docx 文件本质是一个 zip 文件，改一下后缀名就可以解压。
• 主要文字是放在 /word/document.xml，似乎每个文本可以检索到两次，把这两个都改了，然后压缩回去就可以实现改动 .docx 文件。
• 可以看看我新开的开源项目。

selenium 爬虫

cloudflare 等工具的广泛使用使得传统的 requests 爬虫适用性逐步降低，如果没有太高的性能要求，不妨使用 selenium 这样的更上层的库来实现爬虫功能。

关于消除自动化特征

• 使用 undetected_chromedriver 库可以消除大部分的自动化特征。

  1	pip install undetected-chromedriver

• 使用方式和传统 selenium 几乎相同，有两点注意。

  1 2	options = uc.ChromeOptions() driver = uc.Chrome(use_subprocess=True, options=options)

  • uc.ChromeOptions() 是该库准备的消除自动化特征的 options 参数
  • use_subprocess 的功能是让 WebDriver 在独立的进程中运行，不受主进程崩溃的影响。（其实可以不管）

关于配置自动下载

• 用 perfs 可以配置自动下载相关的功能

  1	options.add_experimental_option("prefs", CONFIG.PREFS)

  • 参数值是一个 dict，常用的参数有：

    1	download.prompt_for_download: false # 不要弹出提示框选择下载路径

  • 似乎配置默认下载路径的办法无法生效。

lazy load

• 有时候不太想等待所有资源加载完毕，可以使用 page_load_strategy 来控制

  1	options.page_load_strategy = 'eager'

  • "eager" 不会加载图片等资源，初步解析完成后便会返回。
  • page_load_strategy 是 ChromeOptions 类定义的一个属性。

处理网页

• 用 BeautifulSoup 库可以来层次化读取和处理整个 html 页面。

  1 2 3

  import BeautifulSoup soup = BeautifulSoup(driver.page_source, "html.parser") all_artist = soup.find("div", class_='home-rows-videos-wrapper')

  • BeautifulSoup.find() 可以通过标签名和 class 属性来查找，返回值同样是一个结构化的 HTML 对象，仍然有 find 等方法。

一些关于 HTTP 请求的小知识

• 看 http 请求的时候，有时候 payload 是没有数据的，数据可以通过 headers 传递。

  请求一个超大二进制文件时可能的 headers：

  1 2 3

  headers = { 'Range': f'bytes={0}-' }

压缩文件的处理

Python 一般选用 zipfile 来出来压缩文件。

zipfile 的打开方式和文件流对象差不多，都需要用 with 指定打开模式，文件名，编码等信息。

解压

1
2
3

with zipfile.ZipFile('example.zip', 'r') as zip_ref:
    zip_ref.extractall('extracted/')
    zip_ref.extract("folder/subfolder/file.txt", 'extracted')

• 若不存在，extracted 目录会被自动创建。
• folder/subfolder/file.txt 是以 .zip 文件中，被压缩文件的目录，解压后，extracted 目录会视为其根目录，然后解压过程保持目录结构不变，中间不存在的目录自动创建，也就是说解压出来 folder/subfolder/file.txt 会位于 extracted/folder/subfolder/file.txt。
• extractall 即对每一个压缩文件中的文件做 extract 操作。

压缩

1
2
3

with zipfile.ZipFile('new_example.zip', 'w') as zip_ref:
    zip_ref.write('file1.txt')
    zip_ref.write('file2.txt', "folder1/folder2/file3.txt")

• 注意到 ZipFile.write() 有两个参数，这个函数用于把一个文件添加到压缩文件对象中，第一个参数是被添加的文件的路径，第二个参数是压缩文件中，被压缩文件的路径。

• 第二个参数如果留空则默认为第一个参数。

• 例如，这个 new_example.zip 压缩文件的目录结构如下：

  1 2 3 4 5

  new_example.zip: ├── file1.txt └── folder1/ └── folder2/ └── file3.txt

• 它不支持直接压缩一个文件夹，所以如果要压缩文件夹需要用 os.path.walk() 方法来遍历文件并添加。

  1 2 3 4 5 6 7 8 9 10 11

  with zipfile.ZipFile(zip_file_path, 'w') as zipf: for root, dirs, files in os.walk(folder_path): for file in files: # 创建文件的绝对路径 file_path = os.path.join(root, file) # 创建文件在ZIP中的相对路径 # 这里使用 os.path.relpath() 来获取相对于 folder_path 的相对路径 # 这样ZIP文件中的目录结构会与原始文件夹结构相同 arcname = os.path.relpath(file_path, start=folder_path) zipf.write(file_path, arcname)

  • root 是正在遍历的目录路径，dirs 是该目录下所有子目录的名字列表（相对 root 的路径），filenames 是该目录下所有文件的文件名（相对 root 的路径）。

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。

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