2024年11月

llama.cpp
是
Ollama
、
LMStudio
和其他很多热门项目的底层实现，也是
GPUStack
所支持的推理引擎之一，它提供了
GGUF
模型文件格式。GGUF (General Gaussian U-Net Format) 是一种用于存储模型以进行推理的文件格式，旨在针对推理进行优化，可以快速加载和运行模型。

llama.cpp
还支持量化模型，在保持较高的模型精度的同时，减少模型的存储和计算需求，使大模型能够在桌面端、嵌入式设备和资源受限的环境中高效部署，并提高推理速度。

今天带来一篇介绍如何制作并量化
GGUF
模型，将模型上传到
HuggingFace
和
ModelScope
模型仓库的操作教程。

注册与配置 HuggingFace 和 ModelScope

  • 注册 HuggingFace

访问
https://huggingface.co/join
注册 HuggingFace 账号（需要某上网条件）

  • 配置 HuggingFace SSH 公钥

将本地环境的 SSH 公钥添加到 HuggingFace，查看本地环境的 SSH 公钥（如果没有可以用
ssh-keygen -t rsa -b 4096
命令生成）：

cat ~/.ssh/id_rsa.pub

在 HuggingFace 的右上角点击头像，选择
Settings
-
SSH and GPG Keys
，添加上面的公钥，用于后面上传模型时的认证。

  • 注册 ModelScope

访问
https://www.modelscope.cn/register?back=%2Fhome
注册 ModelScope 账号

  • 获取 ModelScope Token

访问
https://www.modelscope.cn/my/myaccesstoken
，将 Git 访问令牌复制保存，用于后面上传模型时的认证。

image-20241106162218513

准备 llama.cpp 环境

创建并激活
Conda
环境（没有安装的参考
Miniconda
安装：
https://docs.anaconda.com/miniconda/
）：

conda create -n llama-cpp python=3.12 -y
conda activate llama-cpp
which python
pip -V

克隆 llama.cpp 的最新分支代码，编译量化所需的二进制文件：

cd ~
git clone -b b4034 https://github.com/ggerganov/llama.cpp.git
cd llama.cpp/
pip install -r requirements.txt
brew install cmake
make

image-20241106120151035

编译完成后，可以运行以下命令确认量化所需要的二进制文件
llama-quantize
是否可用：

./llama-quantize --help

image-20241106120420296

下载原始模型

下载需要转换为 GGUF 格式并量化的原始模型。

从 HuggingFace 下载模型，通过 HuggingFace 提供的
huggingface-cli
命令下载，首先安装依赖：

pip install -U huggingface_hub

国内网络配置下载镜像源：

export HF_ENDPOINT=https://hf-mirror.com

这里下载
meta-llama/Llama-3.2-3B-Instruct
模型，该模型是
Gated model
，需要在 HuggingFace 填写申请并确认获得访问授权：

image-20241106141024313

在 HuggingFace 的右上角点击头像，选择
Access Tokens
，创建一个
Read
权限的 Token，保存下来：

image-20241106131544469

下载
meta-llama/Llama-3.2-3B-Instruct
模型，
--local-dir
指定保存到当前目录，
--token
指定上面创建的访问 Token：

mkdir ~/huggingface.co
cd ~/huggingface.co/
huggingface-cli download meta-llama/Llama-3.2-3B-Instruct --local-dir Llama-3.2-3B-Instruct --token hf_abcdefghijklmnopqrstuvwxyz

转换为 GGUF 格式与量化模型

创建 GGUF 格式与量化模型的脚本：

cd ~/huggingface.co/
vim quantize.sh

填入以下脚本内容，并把
llama.cpp
和
huggingface.co
的目录路径修改为当前环境的实际路径，需要为绝对路径，将
d
变量中的
gpustack
修改为 HuggingFace 用户名：

#!/usr/bin/env bash

llama_cpp="/Users/gpustack/llama.cpp"
b="/Users/gpustack/huggingface.co"

export PATH="$PATH:${llama_cpp}"

s="$1"
n="$(echo "${s}" | cut -d'/' -f2)"
d="gpustack/${n}-GGUF"

# prepare

mkdir -p ${b}/${d} 1>/dev/null 2>&1
pushd ${b}/${d} 1>/dev/null 2>&1
git init . 1>/dev/null 2>&1

if [[ ! -f .gitattributes ]]; then
    cp -f ${b}/${s}/.gitattributes . 1>/dev/null 2>&1 || true
    echo "*.gguf filter=lfs diff=lfs merge=lfs -text" >> .gitattributes
fi
if [[ ! -d assets ]]; then
    cp -rf ${b}/${s}/assets . 1>/dev/null 2>&1 || true
fi
if [[ ! -d images ]]; then
    cp -rf ${b}/${s}/images . 1>/dev/null 2>&1 || true
fi
if [[ ! -d imgs ]]; then
    cp -rf ${b}/${s}/imgs . 1>/dev/null 2>&1 || true
fi
if [[ ! -f README.md ]]; then
    cp -f ${b}/${s}/README.md . 1>/dev/null 2>&1 || true
fi

set -e

pushd ${llama_cpp} 1>/dev/null 2>&1

# convert

[[ -f venv/bin/activate ]] && source venv/bin/activate
echo "#### convert_hf_to_gguf.py ${b}/${s} --outfile ${b}/${d}/${n}-FP16.gguf"
python3 convert_hf_to_gguf.py ${b}/${s} --outfile ${b}/${d}/${n}-FP16.gguf

# quantize

qs=(
  "Q8_0"
  "Q6_K"
  "Q5_K_M"
  "Q5_0"
  "Q4_K_M"
  "Q4_0"
  "Q3_K"
  "Q2_K"
)
for q in "${qs[@]}"; do
    echo "#### llama-quantize ${b}/${d}/${n}-FP16.gguf ${b}/${d}/${n}-${q}.gguf ${q}"
    llama-quantize ${b}/${d}/${n}-FP16.gguf ${b}/${d}/${n}-${q}.gguf ${q}
    ls -lth ${b}/${d}
    sleep 3
done

popd 1>/dev/null 2>&1

set +e

开始将模型转换为
FP16
精度的 GGUF 模型，并分别用
Q8_0
、
Q6_K
、
Q5_K_M
、
Q5_0
、
Q4_K_M
、
Q4_0
、
Q3_K
、
Q2_K
方法来量化模型：

bash quantize.sh Llama-3.2-3B-Instruct

脚本执行完后，确认成功转换为
FP16
精度的 GGUF 模型和量化后的 GGUF 模型：

image-20241106154934731

模型被存储在对应用户名的目录下：

ll gpustack/Llama-3.2-3B-Instruct-GGUF/

image-20241106171759142

上传模型到 HuggingFace

在 HuggingFace 右上角点击头像，选择
New Model
创建同名的模型仓库，格式为
原始模型名-GGUF
：

image-20241106171458202

更新模型的 README：

cd ~/huggingface.co/gpustack/Llama-3.2-3B-Instruct-GGUF
vim README.md

为了维护性，在开头的元数据之后，记录原始模型和
llama.cpp
的分支代码 Commit 信息，注意按照原始模型的信息和
llama.cpp
的分支代码 Commit 信息更改：

# Llama-3.2-3B-Instruct-GGUF

**Model creator**: [meta-llama](https://huggingface.co/meta-llama)<br/>
**Original model**: [Llama-3.2-3B-Instruct](https://huggingface.co/meta-llama/Llama-3.2-3B-Instruct)<br/>
**GGUF quantization**: based on llama.cpp release [b8deef0e](https://github.com/ggerganov/llama.cpp/commit/b8deef0ec0af5febac1d2cfd9119ff330ed0b762)

---

image-20241106173636107

准备上传，安装 Git LFS 用于管理大文件的上传：

brew install git-lfs

添加远程仓库：

git remote add origin git@hf.co:gpustack/Llama-3.2-3B-Instruct-GGUF

添加文件，并通过
git ls-files
确认提交的文件，
git lfs ls-files
确认所有
.gguf
文件被 Git LFS 管理上传：

git add .
git ls-files
git lfs ls-files

image-20241106181806616

上传超过 5GB 大小的文件到 HuggingFace 需开启大文件上传，在命令行登录 HuggingFace，输入上面下载模型章节创建的 Token：

huggingface-cli login

为当前目录开启大文件上传：

huggingface-cli lfs-enable-largefiles .

image-20241106190029534

将模型上传到 HuggingFace 仓库：

git commit -m "feat: first commit" --signoff
git push origin main -f

上传完成后，在 HuggingFace 确认模型文件成功上传。

上传模型到 ModelScope

在 ModelScope 右上角点击头像，选择
创建模型
创建同名的模型仓库，格式为
原始模型名-GGUF
，并填写 License、模型类型、AI 框架、是否公开模型等其他配置：

image-20241106222426572

上传本地仓库的
README.md
文件并创建：

image-20241106223134251

添加远程仓库，需要使用本文最开始获得的 ModelScope Git 访问令牌提供上传模型时的认证：

git remote add modelscope https://oauth2:xxxxxxxxxxxxxxxxxxxx@www.modelscope.cn/gpustack/Llama-3.2-3B-Instruct-GGUF.git

获取远端仓库已存在的文件：

git fetch modelscope master

由于 ModelScope 使用
master
分支而非
main
分支，需要切换到
master
分支并通过
cherry-pick
将
main
下的文件移到
master
分支，先查看并记下当前的 Commit ID：

git log

image-20241106224107550

切换到
master
分支，并通过
main
分支的 Commit ID 将
main
分支下的文件移到
master
分支：

git checkout FETCH_HEAD -b master
git cherry-pick -n 833fb20e5b07231e66c677180f95e27376eb25c6

修改冲突文件，解决冲突（可以用原始模型的
.gitattributes
合并
*.gguf filter=lfs diff=lfs merge=lfs -text
，参考
quantize.sh
脚本相关逻辑 ）：

vim .gitattributes

添加文件，并通过
git ls-files
确认提交的文件，
git lfs ls-files
确认所有
.gguf
文件被 Git LFS 管理上传：

git add .
git ls-files
git lfs ls-files

将模型上传到 ModelScope 仓库：

git commit -m "feat: first commit" --signoff
git push modelscope master -f

上传完成后，在 ModelScope 确认模型文件成功上传。

总结

以上为
使用 llama.cpp 制作并量化 GGUF 模型，并将模型上传到 HuggingFace 和 ModelScope 模型仓库
的操作教程。

llama.cpp
的灵活性和高效性使得其成为资源有限场景下模型推理的理想选择，应用十分广泛，GGUF 是
llama.cpp
运行模型所需的模型文件格式，希望以上教程能对如何管理 GGUF 模型文件有所帮助。

如果觉得写得不错，欢迎
点赞
、
转发
、
关注
。

看到最大值，考虑使用单调栈搞出
\([la_i, ra_i], [lb_i, rb_i]\)
表示这一段区间
\(i\)
是
\(a, b\)
的最大值。预处理是简单的。

inline void init() {
    static auto f = [] (int a[], int l[], int r[]) -> void {
        static int stack[N], top;
        top = 0, a[n + 1] = 0x3f3f3f3f;
        for (int i = 1; i <= n + 1; ++i) {
            while (top && a[stack[top]] < a[i]) r[stack[top--]] = i - 1;
            l[i] = stack[top] + 1, stack[++top] = i;
        }
    };
    f(a, la, ra), f(b, lb, rb);
}

接下来我们注意到，对于一个随机排列，每个值作为最大值的区间长度和是不大的。

我们记一个随机排列
\(a\)
，这里随机是良定义的，即
\(n!\)
个排列随机选取。我们记
\([l_i, r_i]\)
表示最大的
\(i\)
作为最大值的区间。

我们求的是
\(\sum \limits _ {i = 1} ^ n \Big(r_i - l_i + 1 \Big)\)
的期望，记该期望为
\(\mathbb{E}\)
。

稍微简化一下得到
\(\mathbb{E} = n + \sum \limits _ {i = 1} ^ n \mathrm{E}\Big(r_i - l_i\Big)\)
，注意，这里不能直接把
\(\mathrm{E}\Big(r_i - l_i\Big)\)
拆开，不然你会把这一坨消掉，得到答案
\(\mathbb{E} = n\)
，这显然是荒谬的，问题出在
\(r_i, l_i\)
不是独立的，所以不能直接利用数学期望的线性关系。

考虑
\(\mathrm{E}(r_i - l_i)\)
使用期望定义式求解。先枚举
\(v\)
表示
\(a_i\)
的值。然后枚举
\(r_i\)
，那么要求存在
\(r_i - i\)
个数小于
\(v\)
，所以
\(r_i \in \Big[i, \min\{n, i+v-1\}\Big]\)
，选择小于
\(v\)
的数并排列的方案是
\(\dbinom{n - 1}{r_i - i}(r_i - i)! = \dfrac{(n - 1)!}{(n - 1 - r_i + i)!}\)
。然后对
\(r_i + 1\)
分类讨论，如果
\(r_i + 1 \leq n\)
，那这个位置是比
\(v\)
大的数，方案数是
\(n - v\)
；反之不用限制这个位置必须比
\(v\)
大。对于
\(l_i\)
类似枚举。注意最后对于剩下来的数字随便排列要乘上一个阶乘。

\[\mathbb{E} = n + \sum\limits_{i=1}^n \dfrac{\displaystyle \sum _ {v = 1} ^ n \sum _ {r_i = i} ^ {\min\{n, i+v-1\}} \sum _ {l_i = \max\{1, r_i - v + 1\}} ^ i \dfrac{(r_i - l_i)(v - 1)!}{(v - 1 - r_i + l_i)!} \dfrac{(n - v)!}{(n - v - c)!} \Big(n - r_i + l_i - 1 - c \Big)!}{n!}
\]

其中
\(c = [r_i \neq n] + [l_i \neq 1]\)
，需要额外满足
\(c \leq n - v\)
。

好吧，我承认，这式子比我都丑。并且 OEIS 只有整数数列，找不到这个。但是应该存在这样一个关系：
\(\mathcal{O}(n \log_2 n) \leq \mathcal{O}(\mathbb{E}) \leq \mathcal{O}(n \sqrt{n})\)
。这个增长速率肯定含有对数，于是我们猜测和调和级数相关，事实上，经过我们下面的研究，和我们猜测一致。

可爱的 yzh 马上敲了个简短的 Python 代码
\(\mathcal{O}(n! \cdot n)\)
来验证。

展开她的可爱代码 
import itertools
import fractions

def solve(n: int) -> fractions.Fraction:
    total: int = 0
    count: int = 0
    
    for perm in itertools.permutations(range(n)):
        count += 1
        
        l: list[int] = [0] * n
        r: list[int] = [n - 1] * n
        stack: list[int] = [-1]
        
        for i in range(n):
            while len(stack) > 1 and perm[stack[-1]] < perm[i]:
                r[stack.pop()] = i - 1
            l[i] = stack[-1] + 1
            stack.append(i)
        
        total += sum(r[i] - l[i] + 1 for i in range(n))
    
    return fractions.Fraction(total, count)

def main() -> None:
    while True:
        n = int(input('Input n: '))
        print(f'∑ r[i] - l[i] + 1 = {solve(n)}')

if __name__ == '__main__':
    main()

xym 说，你这太慢了吧……所以 xym 敲了 C++ 代码。

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 20;

using uint = unsigned;
using lint = long long;

lint gcd(lint a, lint b) {
    return b ? gcd(b, a % b) : a;
}

int n, a[N];
lint son, mon;

void solve() {
    static int stack[N], top;
    static int l[N], r[N];
    top = 0, a[n] = 0x3f3f3f3f, stack[0] = -1;
    for (int i = 0; i <= n; ++i) {
        while (top && a[stack[top]] < a[i]) r[stack[top--]] = i - 1;
        l[i] = stack[top] + 1, stack[++top] = i;
    }
    ++mon;
    for (int i = 0; i < n; ++i) son += r[i] - l[i] + 1;
}

void dfs(int i, uint nvis) {
    if (i == n) return solve();
    for (uint st = nvis; st; st &= st - 1) {
        int j = __builtin_ctz(st);
        a[i] = j, dfs(i + 1, nvis ^ (1u << j));
    }
}

signed main() {
    while (true) {
        printf("Input n: "), scanf("%d", &n);
        son = mon = 0;
        dfs(0, (1u << n) - 1);
        lint g = gcd(son, mon);
        son /= g, mon /= g;
        if (mon > 1)
            printf("∑ r[i] - l[i] + 1 = %lld/%lld\n", son, mon);
        else
            printf("∑ r[i] - l[i] + 1 = %lld\n", son);
    }
    return 0;
}

yzh 不服！她表示 Python yyds！所以敲了
\(\mathcal{O}(n ^ 4)\)
的代码。表示：你 C++ 还要手写高精度、分数类，能有我 Python 优雅吗？

展开她的可爱代码 
from fractions import Fraction

def solve(n: int) -> Fraction:
    frac: list[int] = [1] * (n + 1)
    for i in range(2, n + 1):
        frac[i] = frac[i - 1] * i
    
    total: int = 0
    
    for i in range(1, n + 1):
        for v in range(1, n + 1):
            for ri in range(i, min(n, i + v - 1) + 1):
                for li in range(max(1, ri - v + 1), i + 1):
                    c = (ri != n) + (li != 1)
                    if c > n - v:
                        continue
                    # print(f'{i = }, {v = }, {li = }, {ri = }')
                    total += (ri - li + 1) * frac[v - 1] // frac[v - 1 - ri + li] * frac[n - v] // frac[n - v - c] * frac[n - ri + li - 1 - c]
    
    return Fraction(total, frac[n])

def main() -> None:
    while True:
        n = int(input('Input n: '))
        print(f'∑ r[i] - l[i] + 1 = {solve(n)}')

if __name__ == '__main__':
    main()

xym 说，我虽然不会优化时间复杂度，但是这又不是 OI，我开多进程！

from multiprocessing import Pool, cpu_count
from fractions import Fraction
from time import time

def calc(i: int, n: int, frac: list[int], g: list[list[int]]) -> int:
    total: int = 0
    for v in range(1, n + 1):
        for ri in range(i, min(n, i + v - 1) + 1):
            for li in range(max(1, ri - v + 1), i + 1):
                c = (ri != n) + (li != 1)
                if c > n - v or li == ri:
                    continue
                if c == 0:
                    total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c]
                elif c == 1:
                    total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c] * (n - v)
                else:
                    total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c] * (n - v) * (n - v - 1)
    return total

def solve(n: int) -> Fraction:
    frac: list[int] = [1] * (n + 1)
    for i in range(2, n + 1):
        frac[i] = frac[i - 1] * i
    
    g: list[list[int]] = [[0] * (i + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        g[i][0] = 1
        for j in range(1, i + 1):
            g[i][j] = g[i][j - 1] * (i - j + 1)
        for j in range(i + 1):
            g[i][j] *= j
    
    total: int = 0
    
    with Pool(processes=cpu_count()) as pool:
        results = pool.starmap(calc, [(i, n, frac, g) for i in range(1, n + 1)])
        total = sum(results)
    
    return n + Fraction(total, frac[n])

def main() -> None:
    start_time = time()
    with open('res', 'w') as f:
        for n in range(100, 200):
            res = solve(n)
            print(f'\\frac{{{res.numerator}}}{{{res.denominator}}}', file=f, end=', ')
    end_time = time()
    print(f'time used {end_time - start_time:.2f}s.')
    return

if __name__ == '__main__':
    main()

yzh：好厉害！让我来试试看！哇，
\(n \in [100, 200)\)
居然在机房垃圾四核电脑上只跑了
\(3837.22\)
秒！

$n \in [1, 200)$ 
[
    1 / 1,
	3 / 1,
	17 / 3,
	53 / 6,
	62 / 5,
	163 / 10,
	717 / 35,
	3489 / 140,
	3727 / 126,
	43391 / 1260,
	45596 / 1155,
	619313 / 13860,
	644063 / 12870,
	667229 / 12012,
	2756003 / 45045,
	24124223 / 360360,
	24784883 / 340340,
	160941559 / 2042040,
	164719333 / 1939938,
	33664415 / 369512,
	11451017 / 117572,
	268428987 / 2586584,
	819836496 / 7436429,
	20845424563 / 178474296,
	21181779967 / 171609900,
	193553388003 / 1487285800,
	196368607553 / 1434168450,
	5773568883787 / 40156716600,
	5849866645327 / 38818159380,
	183636137408557 / 1164544781400,
	743424203592403 / 4512611027925,
	376019594141039 / 2187932619600,
	34563855136549 / 193052878200,
	34933413503389 / 187537081680,
	35292859576609 / 182327718300,
	1318781072333833 / 6563797858800,
	1331390473483633 / 6391066336200,
	1343680985668633 / 6227192840400,
	1355668331886403 / 6071513019390,
	56062051135874333 / 242860520775600,
	56530424997370133 / 237078127423800,
	350069394209013017 / 1422468764542800,
	3880990797545677687 / 15291539218835100,
	3910554440035425547 / 14951727236194320,
	3939482781861975427 / 14626689687581400,
	186486719509082752469 / 672827725628744400,
	187790323227488444744 / 658810481344812225,
	9264312833874690953831 / 31622903104550986800,
	9325661265897519868223 / 30990445042459967064,
	9385819188627000980759 / 30382789257313693200,
	9444831913915244884859 / 29798504848519199100,
	503645337436905456404827 / 1549522252122998353200,
	506658297371589064313827 / 1520827395602202087400,
	169872332647071722185529 / 497725329469811592240,
	170841119449075462606139 / 488837377157850670950,
	171793065920382856017989 / 480261282821748027600,
	172728747385190744416589 / 471980915876545475400,
	10245273901052056650249751 / 27374893120839637573200,
	10298654942637693943517491 / 26918644902158976946980,
	631421270244256248811257571 / 1615118694129538616818800,
	634573356727960670950532971 / 1589068392611320252031400,
	637675823589725629537832371 / 1563845084792092946443600,
	854306944694613581431806703 / 2052546673789621992207225,
	429158652559393575277521179 / 1010484516327198519240480,
	431133690477669463292400299 / 995174144867695511373200,
	9672108358327174050860236411 / 21893831187089301250210400,
	9714930116384275184187853811 / 21571863081396811525942600,
	29271407806369719881085398433 / 63777682153694921033221600,
	29396229841441951369393274993 / 62866572408642136447032720,
	2095870772307179804193060072583 / 4400660068604949551292290400,
	6313466194824593491193022423849 / 13018619369622975755906359100,
	462744694792051410390185246292277 / 937340594612854254425257855200,
	464581375686900922104937440738277 / 924673829820788656392484100400,
	466393736393349667871466709575061 / 912344845423178140973917645728,
	468182412471876688174165574433133 / 900340307983399481224260834600,
	469948014894025952091891072952933 / 888647576710887799649919784800,
	42881011935863391720878719600703 / 79750423550977110224992801200,
	3399961258583609398034292732641537 / 6220533036976214597549438493600,
	3412169054668675219181983505685227 / 6142776374014011915080070512430,
	30818043874625657849804266130219973 / 54602456657902328134045071221600,
	30925251137088124616018671696886773 / 53936573040123031449483545962800,
	2575587505783854397255815568833538559 / 4422798989290088578857650768949600,
	2584275146655674214107143097129689559 / 4370146620369968476728393021700200,
	2592861199427459916879068292831147599 / 4318733130718557082884529574386080,
	2601348012207592895332643705599417919 / 4268515303617178512153314114218800,
	2609737852631943901373772633341158319 / 4219451909322728184427413951986400,
	28798362026490486912099741793464447409 / 45886539513884669005648126727852100,
	2571084364772583152252865441795709936901 / 4038015477221850872497035152050984800,
	2579025795211119458968776277594743540341 / 3993148638586052529469290317028196080,
	2586880450225481034823446639866700101861 / 3949267884315876128046550862994919200,
	2594650205519624225901451267108027062461 / 3906341059486355735350392701440626600,
	2602336876636678022671011717262474747061 / 3864337392180050834970280951962770400,
	2609942221504266420590900036157295093061 / 3823227419922816251619533282261038800,
	2617467942846640806265140591144482611541 / 3782982920765733975286696089816185760,
	2624915690471898345028986274071308227256 / 3743576848674424246377459672213933825,
	255331845153870954498869763382309759404407 / 359383377472744727652236128532537647200,
	256039610376852992584960391676256491709607 / 355716200151594271247621474159756650800,
	256740263498363708573781464276874194203607 / 352123107220770086689564691592486381600,
	257433946019588625644559906719311392375359 / 348601876148562385822669044676561517784,
	1042808012853280604195170468741643454878011 / 1394407504594249543290676178706246071136,
	1045555815877039860648125624740858704488779 / 1380736842784501998748610725973831893968,
	107972538614420359552502907325681134436819741 / 140835157964019203872358294049330853184736,
	108250146377714820483212844347605296214731961 / 139480973752826711527431771991164210365652,
	542625615772709108572548906347653671147264089 / 690762917633046571373947823194337041810848,
	543987591714079926812333388376404769654230761 / 684246286334621603719476617315145182925840,
	58351048279823157327304482122528805986600043667 / 72530106351469889994264521435405389390139040,
	58494093767349667388126503817581966615675040107 / 71858531292659983605428738829522006155045160,
	6391305804869035641780956094964781592431914081063 / 7760721379607278229386303793588376664744877280,
	6406615591590624545197109076084860480943274429879 / 7690169367065393881846428304555755058701742032,
	583798917082675385566751412976344982590138528437 / 692808051086972421787966513923941897180337120,
	585165975826338072220458025472569903655110443647 / 686622264916553025164859670049620987384084110,
	66276872033452593485523520584821464593214130888641 / 76901693670653938818464283045557550587017420320,
	66428651692013094680559963248727170285162191586641 / 76227117410385044618302315650421080845026039440,
	66579117393336202551241307819619740592569329942753 / 75564272911164305099882295514330462750721465184,
	66728291690721173463895385799557513661275495593849 / 74912856765378405917986758484034510485629038760,
	66876196561770766726861667348359325387106096516529 / 74272575938323889628089435761948745438743320480,
	67022853427818474068245945641007919096319886293409 / 73643147328677077004122576136847484884177699120,
	67168283172543172497623834761950433037057548136209 / 73024297351125168794003899026453808540613180640,
	67312506159811644705991992462527679308925259167973 / 72415761539865792387387199867900026802774737468,
	1632424122469047386761123325746855460557163904315917 / 1737978276956779017297292796829600643266593699232,
	1635857341852216105967423715616002458549190536131613 / 1723732553375166074532560888658866211764408504976,
	1639262764701567043821988043225304121065115343178029 / 1709718467575367976365629499320176242563071850464,
	1642640837480244182162387875703799630576631089979349 / 1695930415417502105588487325938561918026272883928,
	205748999497638645790378840832481778615831375649748841 / 210295371511770261092972428416381677835257837607072,
	206164583208007144163491143488637961455362956614543769 / 208626360626756211401758361524188172455612934134000,
	26235267283934223117825216571799592336117454336514692663 / 26286921438971282636621553552047709729407229700884000,
	105148900108363759174646655444969246549517943255881384777 / 104326219460917277964091790659689347988584942875383375,
	52677563178067669920194813794648269723352340466829152701 / 51758744538749657284510655831163707529220436775384000,
	52779886234578890396518807937329877975929337791838950301 / 51360600349990044536168266170923986702072587261727200,
	6927467492220482063478831420728483327402580050831689834231 / 6676878045498705789701874602220118271269436344024536000,
	6940669501083172686290287400055600379438953709057374712231 / 6626295636063109533719284643112390102547698189903138000,
	6953772627040199737473506737357394053100382616004326030231 / 6576473864363386905646207314968687921325535045618152000,
	6966778340279425838443627968241473921004496547251257450231 / 6527395701196495958589146066349518608479822097516524000,
	6979688078444014463783948723794920746696823306510790131031 / 6479044621928373766303300539932114766935527119016401600,
	6992503247585916908954063340304051179581423724121197572431 / 6431404587943606312139305683020849217178648243141281000,
	959715855562603333837296429461753661740510463878495354574047 / 874671023960330458450945572890835493536296161067214216000,
	961446183023046596265971126138559444999462701936258756610047 / 868332828134530962375214083232206250829511406276872084000,
	133879810967940472895623170406148619573903431205866106991896533 / 119829930282565272807779543486044462614472574066208347592000,
	134116903044285262756821419931474578974933494798839962079632133 / 118974002209118378002009689604001287881512055680021145109200,
	134352319686954369334570077402393134714784146313270642217826933 / 118130214959408318583555720174185675910721190036900427768000,
	134586084408106437908668522172596981017114517118907043768550933 / 117298312037158964227333496792677326080363998557767326164000,
	134818220228431724530181356994920950830266566151017870015434933 / 116478044120815195246722773038882379744137676889531191016000,
	135048749690754171270773829149893738873510171969861733830987433 / 115669168814420645279731642670556807662581165244465002189500,
	135277694873166162479017160056420978899711280896931812835321133 / 114871450408803951174354183065932277954563364104848002174400,
	135505077401715096327574614569476146217032300158755792784830733 / 114084659652579266577269565373699865091860875309609317228000,
	135730918462659998141003086974399592888744759442531958167914733 / 113308573532493693335247323432382178934773386361924900104000,
	135955238814315543087943813094438025175419682430397120301228733 / 112542975062679546758657814490271488536565458075695677806000,
	20290530760976506386397432206345895840255819492261501149835851217 / 16656360309276572920281356544560180303411687795202960315288000,
	20323510354388874000779589292304124997256574634096003011260121457 / 16545317907214729100812814167596445768055609876568273913186080,
	3073797113566977178118861014574034211870391397101590368600320977927 / 2481797686082209365121922125139466865208341481485241086977912000,
	3078711726090074184822161662992895919281100020693215747331770658927 / 2465470069726405356140856848000391425305655024370206606142531000,
	3083594323679140203272558261848739831711607298290497921198837239927 / 2449355886264141268845818567948101285270977540550793491069704000,
	3088445320726611392149168486934611071270098520042887479736345419927 / 2433450977911776715152014551273113614587399764313450676192628000,
	3093265123631249556352727638336164915655120015059947023978868883127 / 2417751294183313639570388650942319333202964927124331639572030400,
	3098054131002420350677261292779377586642041272511750988572636558727 / 2402252888451369321368014364718330106708074126309432077779902000,
	37472430708899105455021190417983821674306668525971318352468729941703 / 28827034661416431856416172376619961280496889515713184933358824000,
	37529537429462544335850673088578011850767399705834724851735447105703 / 28644585074951770895299614323603379247076023126373228066691996000,
	37586286135743109164982870437709678922860663525236030303565685965703 / 28464430451838866675832321151756817113446614175892893298976952000,
	37642681288575814919584363223991597116766679629572018098414284051853 / 28286527761514873759108369144558337006487572837293562715858346050,
	37698727265941797806100857446085473573319906559603674287894773569803 / 28110835042499253425200863746144931186571500956316584065449288000,
	37754428365007490771221162861286168159189594533720820111876311973803 / 27937311369397406181835426315613172352086491691154136015662564000,
	2054331858356178785968594129696529488205875948604245488056299286633963 / 1508614813947459933819113021043111307012670551322323344845778456000,
	2057321491371623447422808835378474678295992521343146433709194884183963 / 1499415943130707129344606234329433799043081096741089665913792002000,
	2060293061149827939733691782279236647097732445698506047774369490151563 / 1490328573778399813409184378363800866927668484033567910362799323200,
	2063246784648461033339785888667680565683390294681921974536474074352363 / 1481350690803831139834430255602573150861839155816498224155794508000,
	345052540114949060675029439822107106182061447972456230659786738398992621 / 245904214673435969212515422430027143043065299865538705209861888328000,
	345539957397605335542575675748709481412021809548975423450470571784785621 / 244440499109903612252917116344134124334475625461577165297898424707000,
	58478140367397119416800016435507187290283735148306474913504322603905614949 / 41066003850463806858490075545814532888191905077544963770046935350776000,
	58559547680912450610395964408795066687832680277783725812272003881630388549 / 40824439121931666818146016277897976812379011518265287512576071025183200,
	58640480340926104616544218791942478466425642177811164013832023110153997349 / 40585699711861890988800133141769918468446970515234496357531766516264000,
	58720943850238574993446433009392150223389249253076832404866432019351939349 / 40349736341444089297004783530480558477351348593634295797313558571402000,
	10172563245656388796495105551375796820204071633349908569500371289937876393377 / 6940154650728383359084822767242656058104431958105098877137932074281144000,
	10186323897119039901431222010310846914112382144990979024170558569050675213377 / 6900268704459829431733760567430916655471647866391851182441737062359988000,
	10200006144207311677504431238407409931709231641046053151943743041968611875297 / 6860838597577201834980996221331311417440381307155326318542069993432216640,
	10213610875290007378870387872959936225372224215342628202427670214853315532157 / 6821856560090967733645876924619201693477651867910125600823080959378624500,
	10227138963722730145393041561098587862628781592775602519297099036416829075657 / 6783314997604578085433188354423612983345009766961480823417300840964056000,
	10240591268184271808674827603172248173769909617762891298682864807185707231657 / 6745206486382080455739743476027974708157678251416753403061023869947404000,
	1835460385307650292314581749901822354126209797358810489922319463960072922886603 / 1200646754576010321121674338732979498052066728752182105744862248850637912000,
	1837841668037559379451473070673642763464013063037502317765380107420293354745403 / 1193976494828365819337665036851129611951777469148003316268501903023689923600,
	333077979476441631009858847540158895717677052521212052706074191626258601891490343 / 214915769069105847480779706633203330151319944446640596928330342544264186248000,
	333504268446957824476565229265953326498911264059372696967014451261744752282894343 / 213734913195099771395720477475878037128510494202428285956196659343471525884000,
	333928234422312038777202642016356297687313719301970956353911169225360490883418343 / 212566962849771357344377742626283075176988578933562557617638207653070042136000,
	334349902582312943915412956560153000526659375993877208166576592843802722217003343 / 211411707616892165184897428807661971507548423613271456761020608698433791907000,
	334769297699585373237698672000003875897163539623423535867286293186463939523110743 / 210268941629773829156870956219512447337237351053199719156906983786550366004800,
	335186444148302505189090528897020005429784187916641980471420157041395321700829943 / 209138463448968593516242617745213993319295214757214774430256946239310847908000,
	335601365912685218281039865855220403245406960775866187323364677506928927714593943 / 208020075943893895155193191981870602980689357993807208791592470590972287224000,
	336014086595276029041108414049950391197065456151034751625913954057622718475947943 / 206913586178234885074580462237286184879728244387457170446956340428254349526000,
	336424629424994749051177026078198974897223647112120976170451565844186715201197943 / 205818805298984965047730830161956628345973068491227238328189375664083691592000,
	112277672421660911669380051715489233121682324207235400247781622640387430596417181 / 68245182809663435778984433158964566241033175341827979024610161404406697738400,
	21470900356822096571011824977825691096846675497036514251376617175486269382358535171 / 12966584733836052798007042300203267585796303314947316014675930666837272570296000,
	21496630923403302488282870202390156955962240036427112831593239725403274595115216296 / 12899050438347323356350755621556375567120280901848632077099493527947495108992375,
	4153790104534724405084076288464356384342919394615840802583024373024035887483980824753 / 2476617684162686084419345079338824108887093933154937358803102757365919060926536000,
	4158705041691439014066042514523868999198185019173906013320855272826024953661592764753 / 2463851613625765022128523712950479654717572830406716032211334186451661746179492000,
	4163594839509250147725343738508032258820624509868097803600166997596059790050164371953 / 2451216477145632893809915899037913092385687841532835437174352985495499378250366400,
	4168459753843993266070711377715816688376430798492364502503538545102987082183528619553 / 2438710270629583746392518368940780882730658821933178113515300164140930503871538000,
	822140107223082840660769616092271732935304554902371679635581575749467559017168909409941 / 477987213043398414292933600312393053015209129098902910248998832171622378758821448000,
	823088839418668979937623772177740270661743833628310411169560649189080930708341721677941 / 475573136209845897049029895260310259818162618345878148076024090594998023310544572000,
	54660843477706005378973832490666045471438399042093464563744199568137376476722555906616753 / 31387826989849829205235973087180477147998732810827957773017589979269869538495941752000,
	54723148314280857289946225897244098718577176526722958059923639484246227167756470350994473 / 31230887854900580059209793221744574762258739146773817984152502029373520190803462043240
]

yzh 想了想，凑到 xym 耳边说道，你为什么要把分母
\(n!\)
约分掉啊？说罢，把未约分前的分子一股脑写在了纸上。

1
6
34
212
1488
11736
103248
1004832
10733760
124966080
1575797760
21403457280
311623441920
4842481190400
80007869491200
1400671686758400
25902542427955200
504597366114508800
10328835149402112000
221649697053388800000
4976042317509795840000
116645883816108810240000
2850081244336603791360000
72467075895142688686080000
1914545944958638638366720000
52483812226093123521085440000
1490921189770317557276344320000
43835602323112218529856225280000
1332446705336234245944272486400000
41827511823053904039590520422400000
1354660802786268583843711470796800000
45221845327160072404359188997734400000
1554646245524132541209081596713369600000
54994400873805035337517574909853696000000
2000169494590713957869118380820135936000000
74739924805469832731163712335309176832000000
2867272655463516432659385028456759689216000000
112855915044919116752189714578432195559424000000
4554509343341692955693109139392993542799360000000
188346315761424009208750056972565064145960960000000
7976634399922888103249496905685018081566392320000000
345771838905576784429706482094891359895562485760000000
15333386431854373306283252333706003318849342013440000000
695258517319960322483196251506730867131352403148800000000
32218477966874346774582910266489920702280658373836800000000
1525154086541852996110535430221131125078049863342489600000000
73719140014871468085641779055492717708791827053464780800000000
3636807068672262913357528787458736305827873300696740659200000000
183044503246089144716950081410532032670130249211240775680000000000
9395489570089938869090807116105941908488510440079821373440000000000
491637281058049872375126843462281520894684684682615723130880000000000
26216541127665243610744819734197258838157804039340382895472640000000000
1424162329286872262230244632516574372792926816195673420527042560000000000
78786340622172397158043342260024256266127841676117287197527244800000000000
4437197037851631551321885275513808357241236497400895148644945100800000000000
254329531929799067053129586898366959745263895988561910953374488985600000000000
14831455692350295459141023198268684584545530238950162871127401876684800000000000
879716481591728312016223637916977107533709028349625668643212926071603200000000000
53058004571263795513877466839548890190030518592204733840749997454262272000000000000
3253041569954028616799340220559208640947024076460438568758107578807877632000000000000
202695416777791482449016530957840962828786747625916902023249032487353974784000000000000
12832243623307762044540546838241705561162363657498293255845915977259461640192000000000000
825197338549245263041301637941838001425392809179548047398159018575583183372288000000000000
53889618261757305985827357098181431156118718855329486196649833716563723597905920000000000000
3573083219527961252233948475704210287327405096038262418772534469667608454307512320000000000000
240477017935936207557015283182370989259972541304789834369332607598334719645125181440000000000000
16424835096540962041389535245354190355779823786289418987427487713560427189661251665920000000000000
1138237221635281853369791662907480872246475472021366595952646372083205651015613787668480000000000000
80016370383783575528030752090867637563856776732081347087800170416932891909155534248345600000000000000
5704948318136145504770956497556099191667656753717974974579529177290568087435868481624473600000000000000
412445257511268231086755130328797304721911996545793244215641406928833451646555898867036979200000000000000
30230122236487785180738651487128512664170843346804180689473582304969410151492645916824410521600000000000000
2245908041964744585969581200253374764696055230972290483723699427737513217033602942789765981798400000000000000
169100210120198208545829604818307489865385432025863373316602861853891943326818096656833933475840000000000000000
12900903462213702707025716967396336043308999638486935682766238677994263966957620109172807324139520000000000000000
997115746852975813552864124534123574417592834990366136121507558276969357700050251385132180087767040000000000000000
78063508943887019146136555349573394227981491493161596005835480206996772039258736910277322732596101120000000000000000
6189520585831458822338068844149675928183017586739518380082254080429394599760559461024318603093585428480000000000000000
496939559011495094546584338353895005512552291623141125969018013597981575126906526402245966782955677286400000000000000000
40394348575810551965334269329940328679195835127942383136737464123489733825799695434406727837343130478182400000000000000000
3323859265800913733326874741984539983372717610323396303377386678780532727035707329585021382785768910277836800000000000000000
276825250602857660847829000264464050404117775887733148211598670341887987943253812760726532850301528141358694400000000000000000
23331756165700755400066588826368232050142122368090803348996119862841253746364578631422174936173727426448824729600000000000000000
1989788299113997708953146927928379866227510297356794740192632656048744316952009620769809761428764160983591550976000000000000000000
171681900306545347672093532302713660683237998175059254019889493399664748251061127536241590170055430975872267452416000000000000000000
14984497807025352657207973408798744937712795525700683289025658352851520862315643200273146233778172792908012314427392000000000000000000
1322827094519606416536347095488484892449470288867230412477153041308866423952982045521921445954317134043448980952580096000000000000000000
118100468939461388422247271589247548607168067863344244047623140865951676202067730856915128289000597518730287837341548544000000000000000000
10661872632231084481725573484711541066980425219205025648649225297770330310692668768401842271010384173509355649493222031360000000000000000000
973185333506831302370565015656729434951679995203990215019109022303802195888186611167920231012115940307979869492440161320960000000000000000000
89801965272199678649105005055204477474111847721759628448574571304280404377863194151103485828892796523130004712743560879800320000000000000000000
8376324398271084888581460952217004016105410234688919367753323868729356728892472535094744589050749408896368902090779707320565760000000000000000000
789675600037590621368920264508684984833260490528195372224827887983403087992424369409817954903680297085519001681625083987561021440000000000000000000
75235498462395376004527396493676340520731905454109349692438457965010170512212029481877948730989278209196123052060498362421267660800000000000000000000
7243159072750768540651802102306461357580054229471152133340208968409010911947674818582396379816526973604495816605885093621801995468800000000000000000000
704559455948078208762381347024711144560486229809664175152019809794779808610555045699342956028901732513131681118011921363318722894233600000000000000000000
69238220524341757748730819288919277670551179965536783849418705938472250242836549138033233759707510930840445242849788684186223339424972800000000000000000000
6873341420047918030495750152663173410633473860302380331443282260986022854435252330387557288650283451320200029459116616977127288830374707200000000000000000000
689191239423221802855463373857699617830687895701761586622036591137729342736319808127135675168392267768625253298477617564417323174608240640000000000000000000000
69794034350478850952238382244951632134876002242724039675548195703062146640354828152902496705320170516020795442008685549285069499205156864000000000000000000000000
7137750073053075571817336535995176084555986138378992752821103147455277694914831684633451898201864852809658128366972198002485577146320289792000000000000000000000000
737101724919713970859618542701773172869427721750360869925544185726637249028888856476975672350695216933817846790268856962971438496450418311168000000000000000000000000
76855675959308473064890335880517348185853831022574760662452331481950222900606143264679149491658187273650978113363935346276317864189630938611712000000000000000000000000
8090344980210516065257106968031305830347268900622126868997315736353002149261937200917563974926403556201331979795110510822310512341735184581787648000000000000000000000000
859729062402050139090637692639054312271968741909040254199821495834787793013852678316741207705380709550017506690447316568103206874297577263712960512000000000000000000000000
92219184393008066262704598487902680969191711713007811643580321324639244650715226567243302961682892460563566036053120871044879842733389402385483300864000000000000000000000000
9984087690452420444323678235975849387504097612826185407938591923161588730914706307814093376727454662191256603428888594758465208677718667234066040881152000000000000000000000000
1090902576696185525000887193878600861098679926951246542651626968678196081764561248565278629665149275877162724715843510319154615544773225028592356156243968000000000000000000000000
120286730711401454637564067855301532395013607395903238391932948154693518207976612714801025522427415862663378941175020084888096040971867316273787734683811840000000000000000000000000
13383447633837696074219898449982405361836579928593893191890560907732247432073455393922734117251282902537316465782315969584902898107409358255899619637508177920000000000000000000000000
1502456157636587222210968694789116461330348046664334694960618388044387961735238552569188372321209092037205357019272426371345207761875624445640520834285295370240000000000000000000000000
170170684231827480669882954424675038031223123599603744640627148865142298047066412814883637965432084496621628061806597049259640001083821133729379235738912785694720000000000000000000000000
19443884406715806961896235262800052645436223610662696340035742637022575120633769718470935928539138882972350139447055580684210235480485046010056899299840519915438080000000000000000000000000
2241111514311775577595841353160172537543607833819175231493932433883075492108317134359428009530931789110352870240094530962359500743280655768741639203851348962023833600000000000000000000000000
260551410839131097951698107195539372123830534925614407330338866874528228430662717094464435367762483675321250856843705818633825432242262673657891427588408926809148620800000000000000000000000000
30552084732498027122803574848569396229000962438138831019538902647960806815073526971670225126039838683548797028208757878292202451935081134338120785681337282254356453785600000000000000000000000000
3613051941669540123299613768829250130585661983785161710700148045725907924996879267625433871753992237871297885708936552033092655208564852900757760603586633233877347126476800000000000000000000000000
430886116291465324083073499003612943741924521565073799314083108330495992254441911050021949205253417752945318791107803126443940123796874351191856642827783555889777857475379200000000000000000000000000
51817357217615015578529631083432111953727049092077323219163367545212424333352851190742126143927991393698678686318138877936644709451961737610865650082198896948468979846873088000000000000000000000000000
6283223483300703063058448362886348871802922159921522685557606351747370764503874545366952954461120328725312201673298788960684474207461274760285708134832225917026626774509813760000000000000000000000000000
768165435164827013314009436723170342153363915376712032822309231709083926956768730615205677118087228484983354594874716849026666645780322878123091926398099467528686021975820206080000000000000000000000000000
94681039979437867320497424152094371310032052591768837527656159124989047947166227512446652486606221278058356374196564346334796166646734081016186901987172633385153768437232403742720000000000000000000000000000
11764642815742337871079588965544750152074757311514932834463961983121797740518764496737398188463968973841283591047765987414675170334396252506256652084071008443039140699284442898759680000000000000000000000000000
1473580489146447490314862882773838449085641855560221999739881490676196538830259017506376069327267443860096620632270408056636696291417423241195711459800292902006635078685688056638341120000000000000000000000000000
186046170926088657858741681755839971475623878207411984879593163502365403380025210494746215537551573805254397839314364090155559015261923358541514859782293531387440478054522189342918574080000000000000000000000000000
23675118904753171593163762152324215558929877163924066678606118920909002871502436746148356989424313349973853773359852683942654165580018953064824926940198473797141546633191134836625149788160000000000000000000000000000
3036416818112892482545724738179502316756866904733653970414028078300375649469851081811668188780963459834307663102866501925315541495907190522994861015205456009070122445248726556434611285524480000000000000000000000000000
392465997841269833432325035379925199083178492764903135742168225560400608919553502160017500829229203327931764034155950808276923634985519274409543003098906052015583364455842493031327249381457920000000000000000000000000000
51119684183332261514588323605332606036451899788602095109183528222494107124003772825497371453127042824545375047761369746577331260991708967879686481946355761876970166282949808860729513785006489600000000000000000000000000000
6709562593952742432881681098748140234471869934591393419677848132928594944997933096116061745938353229471657609318533768255719797279753697141575752801742296815865212300580806689700220275835640217600000000000000000000000000000
887350111684448544768906311481989533601360380181947052345418677102863120831596591016518967003189465356472407946018201294840933754086813012313475922005642059611942962515519657029201698812207510323200000000000000000000000000000
118240367426201769433703433585444026495407892163254977755118732540063211643511071538177431907322388878419478846612660205443212846151317103310361047251685165536839455577073725126014795902225760229785600000000000000000000000000000
15873842824367731218263684121965518029679011605902705317153089384774086070193780917506097994100282564881527761153064282641038109281176980908569189692487098535030089457428967317930702533817915765319270400000000000000000000000000000
2146939794074905845361782920344799017849013007866896921585902921427021692972411939089744847130825455940740893571324561486463606993739395317700363330032905621793993832168381309927245022300740079482568704000000000000000000000000000000
292519913592904643547044817375127879559230637290161512399734938178033446758277544756847972018058173486546780413607676693658755120179172022962825517831623000822550689473424418619955173582572549793428537344000000000000000000000000000000
40148139972596255334050574986036702668483064609266407064854197956070588135124804402215726756401138434737954273593981137097854253167093119908575318245874371891573061642994911316693921168766886995760280240128000000000000000000000000000000
5550432503286013693934472303385084277083683041294609868190501119460424779403133370783065668083784846692675520058873434851285817112749435089716773097501258699186126561529315174164054834721464107416840688369664000000000000000000000000000000
772888662362531526163676254900857584332522174305910429161411620338944484854540750760355663686040288584709425700864395096635996781489544270995943037806602361647550107673233988748882617094183876216370935990583296000000000000000000000000000000
108396035416045973494149396778562344823493729827701546871479653334433313004079902351465878430034151289257089420314264164427576401484524897595063153846046617490518458485581186777931056085787776719022295583492669440000000000000000000000000000000
15310668861381947900996775121539038553975339351922676086350233536009297358163968084838164715378455912016920768821987722587523498820000024139766831755175733379203848628180766035908805759246977176024065220277216215040000000000000000000000000000000
2177897803821913226355793244012906068636396182145662509042137603115844371222435908577819605369743680102510073388991047081848673030032227134629927925198479325205451691297086797409715386717287360826862399278672437575680000000000000000000000000000000
311976560630352147753226706869038915100629727575196122665810297919315641925836348572537531007406710448988017214204985022031031685616752617518142177183783061196053728655360512614843621489842395313117320753741178328842240000000000000000000000000000000
45001442608700521915597418253120666547102860013559646453034257453973884681689351905575971537426690859228471421747895462462399281000109808848964235785276806575419200941534550780089574704889846094244482970073639818950082560000000000000000000000000000000
6536271222219882486613022540366232492315095222320322714468269145752483495480551646598023252634701303866302449955748280208900690862813528962711753400641969129460263823000719630204712744300531691115676413758833026516857651200000000000000000000000000000000
955899633361764502129681545690369006044105897354444134782185442771053047955167325539088883086482070768802433260356879161814852509253929234056719000804893513240692408863600458578839987962651253293302070551691465074383467315200000000000000000000000000000000
140751440752451816778658293967886167515122576165854470492337580964129508634410327991976623303939897740939142525057478221057548933352828231531273273626657236509443876553877911319210331421523482211774538593450698216963104466534400000000000000000000000000000000
20865640649451522570383102684606161345160352742992324494231957496323800781003248393705453610896960646173644492008202503703234807279724393134657634403912550251224739059409757435729705881331132106134049044352270748005065976656691200000000000000000000000000000000
3114075832145118047775132621051278470113096314391470148217818989302687107708691155146655891571068146252630223463714682269457778818631595538675201930020202289760198818524356311150690013430824705922129664689709402260966920451574988800000000000000000000000000000000
467870603025375948246078503028377467626113126090642014199662417416541965899036518163396978483898994528953907167878804832527674065582614467169356697418519777637307583398449130177838832265865860423187655913158623725198497813333278720000000000000000000000000000000000
70762347843696922219994734019065867954673327141020393264086238125725308643476706070136576056216174294088491684054668259091976365295037495654809130835593691075939497326743318642852785551011365215762997507023124938606211166870878289920000000000000000000000000000000000
10773074157950834199756541158822447701659946281706689166660055256236034042375037787577090659465949761356209245447812378497433370066155503375375361027718213585581861313885800903171350336298151446500169651521522348320220671167545831587840000000000000000000000000000000000
1650894390728070304413532623453677388392051097549940815869132590043608685205329833011975591060870674998334453370291598730510360089067132428565279420984447700906028129440683737278570024525726899682525921717218828378227847343838976299499520000000000000000000000000000000000
254637693617256279906094075036592906532393549255585847457179363214963296270233197016939548570361627050873157909934970532795247616027579257056739130364118110937496897057868600458285475835123681848602319927936799059327788704202948073310126080000000000000000000000000000000000
39530437268561160834964275095204466410120837702547967835646610245799757092315893631973891309683271494535047306735450372138745507421721652314884971046247080549802450101148515809639243317276679068640110764936035356168297641665056126326433382400000000000000000000000000000000000
6176295602002329404498218879683319173018544070873117627888533519435330547658836386449999882521853407506760529138930543733407076006144755726852700604690571565270099649938498479330618606573167615069198847623741704008062014569299668865902863974400000000000000000000000000000000000
971167832956720832001760790209629710230508247055985513169635562513064862684121889417799564617335307099563753435451884269682013385958285091957445995197752685621003460294876634322743862231357101396991954674334507995382741183641218784854824242380800000000000000000000000000000000000
153678361876754546052471928086494463489898727195979551576377913541150309005409118699434079896748786369076098005532328944776670136122146895484479932285490471840748881528032008905168232449651617848899343223593700972079351290535056768970263087179366400000000000000000000000000000000000
24471807680105904876831089545006486133935033301122007747636695564903525751616199313394244203027022039361847856144362998666470213002894808199890415826885520333340839599395713748947147995106561933445843989205043224190466920901045110798652336858831257600000000000000000000000000000000000
3921364100643239919598017570118209700368698412358193051138289480295203310344644273829006432373689974947139422109246971768360387473639636955630851061957769359905344760733361623145544111273114553406423653499836922002794295886863305790923453336718934016000000000000000000000000000000000000
632279618228487544281435713091876799300400634681865967516937309830548333471338399862286823059951327739165450148747746524753598109613406203968521947564116776759833300035815181446020664736156474048333733932496422489886417443696942650794440177246562942976000000000000000000000000000000000000
102580640781730327342041848397981599881987235650459879463541430562188761188439863104981845283418550007364362559818782027410219223869338357504311229579389178424754871336603720183415356798530274155036458755776034062535080751244540363008285668589140927578112000000000000000000000000000000000000
16745162424746292873247734115655126417000515281001193419596667150423015240163724010554824679703696345321755457800096403932284081075788123075853008564338690156269893173137056751325637593716590255665989817174608951065113922460302916843556886324546817287520256000000000000000000000000000000000000
2750203143869295241873486476485038920461944483032334021060370890863169896642233356870039458791424118111064593478405529275549778152016795103200070321652452544591992534569399107617507964849494766870396406348248950793890174814114648651799406358584228953911721984000000000000000000000000000000000000
454438958053964028852000335090706809637835641642835788987083129623830689773996654599650075966948902625281634297399100681397874075672530038529046033406179171827296539334958566243430079725342305165398543793772796657443545644556121770310897003779973538997715599360000000000000000000000000000000000000
75545016528422107135309019192310422822099946646073329497641888193581067382645789923595565232874165654688484202256708923090321291307514690743863885346880323649547422652369642451699364251765777937873561714059847401888613695874172663720459397340411674118919563509760000000000000000000000000000000000000
12633970904551387450441804883612885117793740493339831960257585094410454109588979094680672883161191684481220001044174782672689871897734731402761217622583852797827907746653613312733677620662086564986576262509675220693101472826531302952243679139274291461850425899089920000000000000000000000000000000000000
2125505341302657311317259149600921274503776091472224999740254729363988869643429734143634377482662457922617118037711551433220232079524013035684942494397652757441384932596249205004426952590679705375193695241302736132774176253153534147444673693308042005661103250011586560000000000000000000000000000000000000
359714114212628860291084198854682123536479471885925990648829686957190268054307683090528576704262055244916597367609962596234445117209581101416275059651222749019441662741375866741195260059030826345590850913946067798951018644859779459937256364754863214232189249247657328640000000000000000000000000000000000000
61236528168752503035144345041187035197848207965006892970478394005772449618700679775762160239602543198940220176372814824147942563402988836240750604190849563510614826662009520235614636898725976038937785906507789435381284347813857825244574579630195062211817252624509226188800000000000000000000000000000000000000
10485918457407203969891727065946352549396096857192411033343854038950778828709070232170105559230818694776274093959925612920729294704556297428201215065824200926173451511350332443876836331277931015354779691552557380977142305997093285770863238264402695935132447506626914340044800000000000000000000000000000000000000
1806052753398859110469259339662767717218247153600416787654544254728959050126560061733085807793192548055212562589119308357950281802878499136432246146485426320519552206677757059147768463876287600313622015325381700545581359539281581895965338069998362689078683900152346821892505600000000000000000000000000000000000000
312872795536087286174616586061426179748224253285955185026824566536748830325695930951100358676717638055404500809026713288684512544119511264395973199359029693586841024192468230444623397979405510608200897290924123386966757373873750250433918540142056976756068075709849232378481868800000000000000000000000000000000000000
54513508435565904203025316011388433467112889446725152668288454977420632323774747174114052312130538754968490571467477232998818921541009666781832772590663011546288521711601462831019305021791055132821282915430790217693053538681206569235880366236260390165198250003719271968020837171200000000000000000000000000000000000000
9552677899817029968072009157451394407699047654477658429651758097552903315319941696421271312390595052442441262100029817075682074915351106360809405031321037568198805890299197780158909759246606783329395325675723577014688575959225305947925974670592949117579384198077152892147004866560000000000000000000000000000000000000000
1683513783924305399972548665246223297383995891715415872481815582991212067040253117533283180642428974989615455659210310464679615966505899922651262098113067368525915634499675405329715231772027609644683796167789628387031915177059387729819381604950515957688368224367078325043126977167360000000000000000000000000000000000000000
298376621525973149246375856337044937330546307978592363629614583817554203650327443788522468151271403632738971088803408258412078946552195180588400779514980517837742417249984078005926405440077480916298932187576602268295594925511087426923925638962313497521387913515767424075187155076382720000000000000000000000000000000000000000
53180898429605395192459780170261961710804987251774364147605021679704697936644158901058538399848074298198482886962531263858728268428233416674004929554005730624458718878167673732008605967262212368351780082432676007131669712435707639555094007197063574538292084862820904782784382088941404160000000000000000000000000000000000000000
9531816060843303254075562670123937737404300144012763202795421755004006149003423103141011538999714844177699524566087396104025958345288251709424941137870463556747840504866167593959671074020013404259386695850413038931162381384854601655002579477850666789467434049395349173376750394704280944640000000000000000000000000000000000000000
1717952834288609947154381281468762941134188113497256898437525245964412479116096058167989194006479359089652595958024544199427731424286910768398310591243620501758911154262641969237743834115871139092197971761075993437510070149750741016384186104995696727290764282364015180863868183626504155955200000000000000000000000000000000000000000
311350139042000562732592153778882478985129142889374573796528826660238970414914881845949842279518558074088740658859511535984596612992902476895667693936611844465136738308358287046056901214053854389703219836011600193791165766186528068510306442775703913387521285383290006996941735262969408992051200000000000000000000000000000000000000000
56738248784206289899507931420376957704142736068894563698804743608156268810318684445082637324730844698298713805382905600808287826164427516464805293361533395682536119753055942192519854252700127293763645742278762524675250561169973800715447009019693300864657241374008652545734738380107392733308518400000000000000000000000000000000000000000
10396299001504131672500312123617223226575519853619213166495288503118617619787540229585900989040123709330224829012292185214470888012271274051293330656612957220029225363085012558975964481485580446277358687124509286247686343307522546410917024111703462530348391862669398629729174797707331630244508467200000000000000000000000000000000000000000
1915334556379919193706301671938708966221677542141842872989566629169783044241384673441325771963419141512479947768361638596011394240539860403660788526115900746024251899945272455205266537623181508934266403463907896794476303811695206265938623377767887965646565898318306826263283989482364722527133813964800000000000000000000000000000000000000000
354781358927184391419936848987489839086152820507821845764587939515886836031741792013759350133915344603730586226661253295681096031998892733152376080729726490481687548897975070308695163799348109960199469721428964503297415766171782331686431093388165394775176325855812078437776173772817832023070907301888000000000000000000000000000000000000000000
66071560180961685437104620424026657972026695723352677357717536064287399862737013531974328316311740802753273925664350928125641943335427192906471216110906098191754852828593757979965156396392061541688455935577681730517120866552122233408201258406032826644206264585599469550070630149397337494461491202490368000000000000000000000000000000000000000000
12370676276892375417458633438196469485901582554356927541267649019737753512125251653303819033773542982954536700397147535866747178676802556822864513374277303239874195660596366222297853058417654922577001749744199024362399212584871945310223685525409089609110936584719779558990088354308518386164349554776866816000000000000000000000000000000000000000000
2328547257091721125168683938522946893630923020283399994091821962070873734642438402630623264841080155682544370878428349702658816332412958069832515800131178428910356053643511615771829850613834284161471720490270517746030752300236543863540343722488772513161192364741877119177567113210546585186876469555293585408000000000000000000000000000000000000000000
440633141260968838464892168553647942650895826683452331712810019031146736959211039901856853932248980527103538691636881642863342198956966439200412130767457763451342172879318220754430325622974399559143629252091616377481625819976418177430124012921140577705198821045788285354000034248973538225606543019848983642112000000000000000000000000000000000000000000
83821925401226274488832394276265511773245329509154035569488570120786131969981406716253399781085812138185681965722294033379328610730332687690772906175432781462392887688738369091011222129287474860969777826840647923962300967690673523793524972116889158041166648004646793104383683302299975565334132867245519698657280000000000000000000000000000000000000000000
16029297447918017055946833350603761225146981531604817788528762029436776551804754795913324297060020706415633437635270533857163476466634213854954752368212461865985151927285139522629061484917059053750619785596784662287463082138233712524747664304271678900829937940394144671010376594299738520138365896564985343487508480000000000000000000000000000000000000000000
3081313312939531524670274998337990596417484773508361370147968387281359801808037932762469284362673654436352424005332345446066445050044463355482657690658113300740665028394174432645418349259151661830824388951514822939678235805425616550584132884841745623013355895994629060065156444150247638395536100437832814859292508160000000000000000000000000000000000000000000
595401614041992531502880965846815840432244516037800385013516906401026112834468746742230095233279428570229941621748700562617089863962711715761365265127143130811081682727515556480945298941337263630405882404188132138764311345418072233734892036930766829774052316352668787931707346451663886794385006262445188180259771514880000000000000000000000000000000000000000000
115644586889508130902924449189185102812851997613084597071998180222767979118715783105992416141383806814885468325956453442676753502671328242310147303980261086797037616474544693521976121396543731480983954849277937361654380742632649134654703918141995474170527832226799315722324720589823414309162179867284027569962077619486720000000000000000000000000000000000000000000
22577209508931025152555679757337607407664898430986062714333061702803260078732578626090446845389936868484058189062877820035778315920524152701316070967509509335229865682582059404580073881477009627959027802604217418326492523722599509241499168065343606648801157035074214382401808679413442488118071149274001881222895307744870400000000000000000000000000000000000000000000
4430303570032865234428944535997826095045149288541306998174533256718240536743980106994247077075474795535664341805487729841577123103632957615744490492086819674998426010872594433909573317885225170786658442859486437271522852107418062320966546163936477861502449792769950195497649095000823262241033184295282723170305511625483878400000000000000000000000000000000000000000000
873783235819611703878491139760995645002621947257052931472181836690604632633843087807707828233162754320149506395938112500127392177775238935548238628764440515626086257923806026951144046286342910640386886284830566512535732082562614430358805261949677886578288053120294819466296456051948035664777515507764942313103840795463306444800000000000000000000000000000000000000000000
173208729491240192305707603189041292438861408349626898591921151541979730371090576732182427264102376627307272479463466186470551643270144703765336676148678929230199751187973880919756088254010439025729697983223987164796352464332011362999212397078484001476868460953024961960382143981901927647655944369546158243524972082984743495270400000000000000000000000000000000000000000000
34508068138962510193218228073132898366290044127266128110259978729544632043904832028276649631335868142789041644863266984616846386941999068326914741690592381753466496061329642705842076735716044647732878469720770992004093744969710758732788221852859089819578251943533902855934633181331297580616164385029156137976097890011827393894809600000000000000000000000000000000000000000000
6909480390941844295676567428594697197623113573773371546311493554594806074651204373673906830808700208851525875535948650607178631262463289216405802229327176689453400839259307763202165261831920919770488164062329596672599403770255946546978528217914426175965560125872358839748688187388519707546668897740528264857333207336049158358302720000000000000000000000000000000000000000000000

不看不知道，一查吓一跳。这串数字出现在了 OEIS 上！是
A063090
号序列。

这个序列和我们的问题不同，但也是和一个排列相关。我们不妨记这个序列为
\(a_i = \mathbb{E}(n) \cdot n!\)
。那么
\(\dfrac{a_i}{n \cdot n!}\)
为，在一个按照随机排列顺序插入
\(n\)
个节点的二叉搜索树中，寻找一个节点的比较次数的期望。

\(\sum\limits_{i=1}^n \Big(r_i - l_i + 1\Big)\)
在转变计数视角后，也可以看做对每个
\(i\)
计算，其在多少个
\(j\)
的
\(l_j \sim r_j\)
之中包含。

二叉查找树此时为笛卡尔树。一个数的
\(l_i \sim r_i\)
可以看做笛卡尔树上的子树。比较次数就是从根一路往下找的结点个数，于是和我们的问题等价。

有一个很有意思的结论，
\(a_n \bmod n \in \{-2, 0\}\)
，并且
\(a_n \bmod n = -2\)
当且仅当
\(n \in \mathbb{P}\)
，不过和我们解决这个问题没有什么帮助。

作者太菜了，目前还不会证明。

根据下文求出的通项公式：
\(a_n = 2(n+1)!\cdot H_{n} - 3n\cdot n!\)
，有
\(a_n \equiv 2(n+1)!\cdot H_{n} \pmod n\)
。

对于
\(H_n\)
中
\(i < n\)
的
\(\dfrac{1}{i}\)
，
\((n+1)! \dfrac{1}{i} \equiv 0 \pmod n\)
。故
\(a_n \equiv 2(n+1)!\dfrac{1}{n} \equiv 2(n+1)(n-1)! \equiv 2(n-1)!\pmod n\)
。

当
\(n \in \mathbb{P}\)
时，由威尔逊定理得
\((n - 1)! \bmod n = -1\)
，所以
\(a_n \equiv -2 \pmod n\)
。

对于
\(n \not \in \mathbb{P}\)
需要小心讨论。

  1. 当
    \(n\)
    为非完全平方数。
    \(n\)
    一定可以分解成
    \(a \times b\)
    的形式，其中
    \(1 \lt a \lt b \lt n\)
    ，那么
    \((n-1)!\)
    中包含
    \(ab\)
    ，所以
    \(a_n \equiv 0 \pmod n\)
    。
  2. 当
    \(n\)
    为完全平方数。
    假设
    \(n = k^2\)
    ，其中
    \(1 \leq k\)
    。如果
    \(k \gt 2\)
    ，那么
    \(\dfrac{n}{k} = k \gt 2\)
    ，即
    \(2k \lt n\)
    ，那么
    \((n-1)!\)
    包含
    \(k \times 2k\)
    ，所以此时结论成立。否则当
    \(k \leq 2\)
    的时候，即
    \(n \in \{1, 4\}\)
    时，验证发现，结论依然成立。

综上所述，
\(a_n \bmod n \in \{-2, 0\}\)
，并且
\(a_n \bmod n = -2\)
当且仅当
\(n \in \mathbb{P}\)
。

我们更关注的当然是
\(a_n\)
的公式。我们有

\[a_n = n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i
\]

使用二叉搜索树的角度思考问题。
\(a_1 = 1\)
显然。

考虑枚举排列
\(p\)
第一个插入二叉搜索树的
\(p_1\)
，即根节点，对于
\(n!\)
的每个排列的
\(n\)
个数，都会多一次查找的贡献，所以是
\(n \cdot n!\)
。

接下来考虑子树的子问题。左右子树此时是对称的，所以只需要计算左子树，然后乘二就可以了。

左子树没有节点的情况，对答案没有贡献。从
\(i = 1\)
开始枚举，表示左子树的大小。对于左子树，是一个
\(a_i\)
的子问题，对于一个确定的左子树，右子树有
\(A_{n - 1}^{n - 1 - i} = \dfrac{(n-1)!}{i!}\)
中方式，所以用
\(a_i \cdot \dfrac{(n-1)!}{i!}\)
就能得到，每一种情况下，左子树对
\(a_n\)
造成的贡献。

所以得到：

\[a_n = n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i
\]

进一步，可以得到递推式如下：

\[\begin{aligned}
a_1 &= 1 \\
a_n &= (2n - 1)(n - 1)! + (n + 1) \cdot a_{n-1}
\end{aligned}
\]

此处证明在下文推出通项公式后给出。

看到
\(a_n = f(n) + g(n) \cdot a_{n - 1}\)
的形式，显然可以求通项公式。

\[a_n = 2(n+1)!\cdot H_{n} - 3n\cdot n!
\]

对于一般的数列我们有：

\[a_n = \sum _ {i = 2} ^ n f(i) \prod _ {j = i + 1} ^ n g(j) + \prod _ {i = 2} ^ n g(i) a_1
\]

此时，
\(f(n)=(2n-1)(n-1)!\)
，
\(g(n)=n+1\)
，
\(a_1=1\)
，所以：

\[\begin{aligned}
a_n &= \sum _ {i = 2} ^ n (2i-1)(i-1)! \prod _ {j = i + 1} ^ n (j+1) + \prod _ {i = 2} ^ n (i+1) \\
&= \sum _ {i = 2} ^ n (2i-1)(i-1)! \prod _ {j = i + 2} ^ {n+1} j + \prod _ {i = 3} ^ {n+1} i \\
&= \sum _ {i = 2} ^ n (2i-1)(i-1)! \dfrac{(n+1)!}{(i+1)!} + \dfrac{(n+1)!}{2} \\
&= (n+1)! \sum _ {i = 2} ^ n \dfrac{2i-1}{i(i+1)} + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\sum_{i=2}^n\dfrac{1}{i+1} - \sum_{i=2}^n\dfrac{1}{i(i+1)}\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\sum_{i=3}^{n+1}\dfrac{1}{i} - \sum_{i=2}^n\Big(\dfrac{1}{i}-\dfrac{1}{i+1}\Big)\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\Big(H_{n+1}-\dfrac{1}{2}-\dfrac{1}{1}\Big) - \Big(\dfrac{1}{2}-\dfrac{1}{n+1}\Big)\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2H_{n+1}+\dfrac{1}{n+1} - \dfrac{7}{2}\Bigg) + \dfrac{(n+1)!}{2} \\
&= 2(n+1)!\cdot H_{n+1}+n! -3(n+1)! \\
&= 2(n+1)!\cdot H_{n} + 3n! -3(n+1)\cdot n! \\
&= 2(n+1)!\cdot H_{n} - 3n\cdot n! \\
\end{aligned}
\]

（其中
\(H_n\)
为调和级数
\(\sum\limits_{i=1}^n\dfrac{1}{i}\)
，对于空和、空积，令结果为该运算的幺元。）

注意对于
\(n = 1\)
上式及推导过程仍然成立。

通项公式和递推式是本质相同的，我们证明通项公式正确性，即说明了递推式正确性。

使用第二数学归纳法，对于
\(a_2\)
显然。假设对于
\(i \lt n\)
成立，推出
\(a_n\)
成立即证。

\[\begin{aligned}
a_n &= n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i \\
&= n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} \Big(2(i+1)!\cdot H_{i} - 3i\cdot i!\Big) \\
&= n \cdot n! + 2 (n-1)! \sum_{i=1}^{n-1} \Big(2(i+1)\cdot H_{i} - 3i\Big) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} (i+1)\cdot H_{i} - 3 \sum_{i=1}^{n-1} i\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \sum_{j=i}^{n-1}(j+1) - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \dfrac{(n+i+1)(n-i)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \dfrac{n(n+1) - i(i+1)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(\sum_{i=1}^{n-1} \Big(\dfrac{n(n+1)}{i} - (i+1)\Big) - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)\sum_{i=1}^{n-1} \dfrac{1}{i} - \sum_{i=2}^ni - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)H_{n-1} - \dfrac{(n+2)(n-1)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)H_{n-1} - \dfrac{(n+2)(n-1) + 3n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Big(n(n+1)H_{n-1} - (2n^2 - n - 1)\Big) \\
&= n \cdot n! + 2 (n+1)!H_{n-1} - 2 (n-1)!(n-1)(2n + 1) \\
&= n \cdot n! + 2 (n+1)!\Big(H_{n} - \dfrac{1}{n}\Big) - 2\dfrac{n!}{n}(n-1)(2n + 1) \\
&= n \cdot n! + 2 (n+1)!H_{n} - 2(n+1)\dfrac{n!}{n} - 2(n-1)(2n+1)\dfrac{n!}{n} \\
&= n \cdot n! + 2 (n+1)!H_{n} - 2(n+1 + (n-1)(2n+1))\dfrac{n!}{n} \\
&= n \cdot n! + 2 (n+1)!H_{n} - 4n^2\dfrac{n!}{n} \\
&= 2 (n+1)!H_{n} - 3n \cdot n! \\
\end{aligned}
\]

证毕。

所以
\(\mathbb{E}(n) = \dfrac{a_n}{n!}\)
为：

\[\begin{aligned}
\mathbb{E}(n) &= \dfrac{2(n+1)!\cdot H_{n} - 3n\cdot n!}{n!} \\
&= 2(n+1)H_{n} - 3n \\
\end{aligned}
\]

也就是说
\(\mathbb{E}(n) = \mathcal{O}(n \log n)\)
。

考虑一个枚举区间内
\(\max a, \max b\)
出现的位置
\(i, j\)
，那么我们只需要枚举每一个
\(i\)
，以及
\(j \in [la_i, ra_i]\)
，由上面的分析，总的时间复杂度为
\(\mathcal{O}(n \log n)\)
。那么我们可能需要稍微讨论一下
\(j\)
的关系。

  1. \(rb_j \lt i\)
    或
    \(lb_j \gt i\)
    ：
    此时直接跳过这种情况，因为不可能存在一个区间，包含
    \(i, j\)
    的同时，让
    \(i, j\)
    分别成为最大值。
  2. \(j < i\)
    ：

    只要区间左端点属于红色区域，右端点属于蓝色区域，就能有
    \(a_i \times b_j\)
    的贡献。形式化地表达红蓝区域如下：
    \(\Big[\max\{lb_j, la_i\}, j \Big]\)
    、
    \(\Big[i, \min\{rb_j, ra_i\}\Big]\)
    。
  3. \(j > i\)
    ：

    这是类似的，红蓝区域如下：
    \(\Big[\max\{lb_j, la_i\}, i \Big]\)
    、
    \(\Big[j, \min\{rb_j, ra_i\}\Big]\)
    。

好吧，发现根本不用分类讨论：
\(L = \Big[\max\{lb_j, la_i\}, \min\{i, j\} \Big]\)
、
\(R = \Big[\max\{i, j\}, \min\{rb_j, ra_i\}\Big]\)
。我们发现，如果把一个区间
\([l, r]\)
映射到二维笛卡尔坐标系的一个点
\((l, r)\)
，那么
\(L \times R\)
就是一个矩形，而我们求的便是一个三角形！

二维笛卡尔坐标系

（事实上，这些矩形是稠密的，能够恰好完全覆盖整个上三角。）

如果我们查询为
\((L, R)\)
，那么想想枚举
\(l = L \sim R\)
，每次
\(r = l \sim R\)
的过程，就是上图粉色三角形内每一个点的点权和！点权就是区间对应的
\(\max a_i \times \max b_j\)
。而我们处理出了不多的矩形，每个矩形内的权值相同！所以可以直接上扫描线和历史版本和了。

我们这里使用历史版本和的原因是，平常我们扫描线相当于一维问题的区间加、单点查询，而这里是区间加、区间查询，所以使用历史版本和。我们从下往上扫，一个
\([l, r]\)
的查询，在扫描到
\(r\)
时，查询
\([l, r]\)
的历史版本和。

#include <cstdio>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

const int N = 250010;

using ull = unsigned long long;

int n, q, a[N], b[N];
int la[N], ra[N], lb[N], rb[N];

vector<tuple<int, int, ull>> line[N];
vector<pair<int, int>> qry[N];

ull ans[N];

inline void initLR() {
    static auto f = [] (int a[], int l[], int r[]) -> void {
        static int stack[N], top;
        top = 0, a[n + 1] = 0x3f3f3f3f;
        for (int i = 1; i <= n + 1; ++i) {
            while (top && a[stack[top]] < a[i]) r[stack[top--]] = i - 1;
            l[i] = stack[top] + 1, stack[++top] = i;
        }
    };
    f(a, la, ra), f(b, lb, rb);
    for (int i = 1; i <= n; ++i) {
        for (int j = la[i]; j <= ra[i]; ++j) {
            if (rb[j] < i || lb[j] > i) continue;
            int ll = max(lb[j], la[i]), lr = min(i, j);
            int rl = max(i, j), rr = min(rb[j], ra[i]);
            ull v = 1ull * a[i] * b[j];
            line[rl].emplace_back(ll, lr, v);
            line[rr + 1].emplace_back(ll, lr, -v);
            
            // printf("[%d, %d] x [%d, %d]: %llu\n", ll, lr, rl, rr, v);
        }
    }
}

struct History_Segment_Tree {
    #define lson (idx << 1    )
    #define rson (idx << 1 | 1)
    
    struct node {
        int l, r, len;
        ull sum, sumh;
        ull cnt, add, hadd;
    } tr[N << 2];
    
    void build(int idx, int l, int r) {
        tr[idx].l = l, tr[idx].r = r, tr[idx].len = r - l + 1;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
    }
    
    inline void pushtag(int idx, ull c, ull a, ull h) {
        tr[idx].cnt += c;
        tr[idx].sumh += h * tr[idx].len + tr[idx].sum * c;
        tr[idx].hadd += h + tr[idx].add * c;
        tr[idx].sum += a * tr[idx].len;
        tr[idx].add += a;
    }
    
    inline void pushdown(int idx) {
        if (!tr[idx].cnt && !tr[idx].add && !tr[idx].hadd) return;
        pushtag(lson, tr[idx].cnt, tr[idx].add, tr[idx].hadd);
        pushtag(rson, tr[idx].cnt, tr[idx].add, tr[idx].hadd);
        tr[idx].cnt = tr[idx].add = tr[idx].hadd = 0;
    }
    
    inline void pushup(int idx) {
        tr[idx].sum = tr[lson].sum + tr[rson].sum;
        tr[idx].sumh = tr[lson].sumh + tr[rson].sumh;
    }
    
    void modify(int idx, int l, int r, ull v) {
        if (l <= tr[idx].l && tr[idx].r <= r) return pushtag(idx, 0, v, 0);
        pushdown(idx);
        if (l <= tr[lson].r) modify(lson, l, r, v);
        if (r >= tr[rson].l) modify(rson, l, r, v);
        pushup(idx);
    }
    
    ull query(int idx, int l, int r) {
        if (l <= tr[idx].l && tr[idx].r <= r) return tr[idx].sumh;
        pushdown(idx);
        if (r <= tr[lson].r) return query(lson, l, r);
        if (l >= tr[rson].l) return query(rson, l, r);
        return query(lson, l, tr[lson].r) + query(rson, tr[rson].l, r);
    }
    
    inline void knock() {
        pushtag(1, 1, 0, 0);
    }
    
    void output(int idx) {
        if (tr[idx].l == tr[idx].r) {
            printf("%llu ", tr[idx].sumh);
            return;
        }
        pushdown(idx);
        output(lson), output(rson);
    }
    
    void output() {
        output(1), puts("");
    }
    
    #undef lson
    #undef rson
} yzh;

signed main() {
    // freopen("yzh", "r", stdin);
    // freopen("out", "w", stdout);
    scanf("%*d%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    initLR();
    scanf("%d", &q);
    for (int i = 1, l, r; i <= q; ++i) {
        scanf("%d%d", &l, &r);
        qry[r].emplace_back(l, i);
    }
    yzh.build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        for (auto [l, r, v]: line[i]) yzh.modify(1, l, r, v);
        yzh.knock();  // , yzh.output();
        for (auto [l, idx]: qry[i]) ans[idx] += yzh.query(1, l, i);
    }
    for (int i = 1; i <= q; ++i) printf("%llu\n", ans[i]);
    return 0;
}

但是其实可以不使用历史版本和，注意到被完全包含的矩形可以直接使用线段树维护面积，对于没有完全包含的矩形，数量不多，可以暴力搞。但是不如直接历史版本和来的好。

时间复杂度：
\(\mathcal{O}((q + \mathbb{E}(n)) \log n) = \mathcal{O}(q \log n + n \log^2 n)\)
。

参考资料：

  1. OEIS A063090
    。

配置环境变量

  1. 配置HarmonyOS SDK和环境变量
  • API12, deveco-studio-5.0 或 command-line-tools-5.0
  • 配置 Java17
  • 配置环境变量 (SDK, node, ohpm, hvigor)
 export TOOL_HOME=/Applications/DevEco-Studio.app/Contents # mac环境
 export DEVECO_SDK_HOME=$TOOL_HOME/sdk # command-line-tools/sdk
 export PATH=$TOOL_HOME/tools/ohpm/bin:$PATH # command-line-tools/ohpm/bin
 export PATH=$TOOL_HOME/tools/hvigor/bin:$PATH # command-line-tools/hvigor/bin
 export PATH=$TOOL_HOME/tools/node/bin:$PATH # command-line-tools/tool/node/bin
  1. 通过代码工具下载Flutter仓库代码
    git clone https://gitee.com/harmonycommando_flutter/flutter.git
    ，指定dev或master分支，并配置环境
 # 依赖缓存
 export PUB_CACHE=D:/PUB
 # 拉取下来的flutter_flutter/bin目录
 export PATH=<flutter_flutter path>/bin:$PATH
 # 国内镜像
 export PUB_HOSTED_URL=https://pub.flutter-io.cn
 export FLUTTER_STORAGE_BASE_URL=https://storage.flutter-io.cn

 # HamonyOS SDK
 export TOOL_HOME=/Applications/DevEco-Studio.app/Contents # mac环境
 export DEVECO_SDK_HOME=$TOOL_HOME/sdk # command-line-tools/sdk
 export PATH=$TOOL_HOME/tools/ohpm/bin:$PATH # command-line-tools/ohpm/bin
 export PATH=$TOOL_HOME/tools/hvigor/bin:$PATH # command-line-tools/hvigor/bin
 export PATH=$TOOL_HOME/tools/node/bin:$PATH # command-line-tools/tool/node/bin

构建步骤

  1. 运行 flutter doctor -v 检查环境变量配置是否正确，Futter与OpenHarmony应都为ok标识，若两处提示缺少环境，按提示补上相应环境即可。
    img1
  2. 创建工程与编译命令，编译产物在
    <projectName>/ohos/entry/build/default/outputs/default/entry-default-signed.hap
    下。
 # 创建工程
 flutter create --platforms ohos <projectName>

 # 进入工程根目录编译
 # 示例：flutter build hap --release
 flutter build hap --release
  1. 通过flutter devices指令发现ohos设备之后，使用 hdc -t
    install 进行安装。
  2. 也可直接使用下列指令运行：
   # 示例：flutter run -d <device-id>
   flutter run --debug -d <device-id>
  1. 构建app包命令：
 # 示例：flutter build app --release
 flutter build app --release

已兼容OpenHarmony开发的指令列表

指令名称 指令描述 使用说明
doctor 环境检测 flutter doctor
config 环境配置 flutter config --"key" "value"
create 创建新项目 flutter create --platforms ohos,android,ios --org "org" "appName"
create 创建module模板 flutter create -t module "moduleName"
create 创建plugin模板 flutter create -t plugin --platforms ohos,android,ios "pluginName"
create 创建plugin_ffi模板 flutter create -t plugin_ffi --platforms ohos,android,ios "pluginName"
devices 已连接设备查找 flutter devices
install 应用安装 flutter install -t "deviceId" "hap文件路径"
assemble 资源打包 flutter assemble
build 测试应用构建 flutter build hap --debug
build 正式应用构建 flutter build hap --release
run 应用运行 flutter run
attach 调试模式 flutter attach
screenshot 截屏 flutter screenshot

附：
Flutter三方库适配计划

运行到手机上

在项目根目录下执行
flutter run
就可以运行到手机上了，若连接的是Android手机，则可以直接运行并在手机上查看效果。若连接的是鸿蒙NEXT手机，则需先配置证书，配置证书的地方在
ohos/build-profile.json5
文件中，证书配置完成后，就直接直接运行并在鸿蒙NEXT手机上查看效果了。
harmony
android
鸿蒙平台ohos下的flutter.har包可以拷贝到其它项目中直接使用。

从事软件开发这么多年，平时也积累了一些方便自己快速开发的帮助类，一直在想着以什么方式分享出来，因此有了这个系列文章，后面我将以《开源-Ideal库》系列文章分享一些我认为比较成熟、比较方便、比较好的代码，如果感觉有借鉴的地方可以集成到自己的公共代码库中，同时我也会以Nuget包的方式发布出来，以供直接下载使用。

主要包括：公共、文档、ORM、SqlSugar、定时任务、Redis、Mqtt、SignalR等库封装，后面可能还会适当删减。

今天我们将分享公共库中关于时间转换的相关封装，主要是关于本地与UTC的日期、时间与时间戳和字符串之间的相互转换。

01
、日期时间转时间戳（秒）

该方法是把日期时间DateTime转成10位时间戳，即秒级时间戳，代码如下：

/// <summary>
/// 日期时间转时间戳（秒）
/// </summary>
/// <param name="dateTime">日期时间</param>
/// <returns>时间戳（秒）</returns>
public static long ToUnixTimestampBySeconds(this DateTime dateTime)
{
    var dto = new DateTimeOffset(dateTime);
    return dto.ToUnixTimeSeconds();
}

02
、日期时间转时间戳（毫秒）

该方法是把日期时间DateTime转为13位时间戳，即毫秒级时间戳，代码如下：

/// <summary>
/// 日期时间转时间戳（毫秒）
/// </summary> 
/// <param name="dateTime">日期时间</param>
/// <returns>时间戳（毫秒）</returns>
public static long ToUnixTimestampByMilliseconds(this DateTime dateTime)
{
    var dto = new DateTimeOffset(dateTime);
    return dto.ToUnixTimeMilliseconds();
}

03
、时间戳（秒）转本地日期时间

该方法是把10位秒级时间戳转为本地日期时间DateTime，代码如下：

/// <summary>
/// 时间戳（秒）转本地日期时间
/// </summary>
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>本地日期时间</returns>
public static DateTime ToLocalTimeDateTimeBySeconds(this long timestamp)
{
    var dto = DateTimeOffset.FromUnixTimeSeconds(timestamp);
    return dto.ToLocalTime().DateTime;
}

04
、时间戳（毫秒）转本地日期时间

该方法是把13位毫秒级时间戳转为本地日期时间DateTime，代码如下：

/// <summary>
/// 时间戳（毫秒）转本地日期时间
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>本地日期时间</returns>
public static DateTime ToLocalTimeDateTimeByMilliseconds(this long timestamp)
{
    var dto = DateTimeOffset.FromUnixTimeMilliseconds(timestamp);
    return dto.ToLocalTime().DateTime;
}

05
、时间戳（秒）转UTC日期时间

该方法是把10位秒级时间戳转为UTC日期时间DateTime，代码如下：

/// <summary>
/// 时间戳（秒）转UTC日期时间
/// </summary> 
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>UTC日期时间</returns>
public static DateTime ToUniversalTimeDateTimeBySeconds(this long timestamp)
{
    var dto = DateTimeOffset.FromUnixTimeSeconds(timestamp);
    return dto.ToUniversalTime().DateTime;
}

06
、时间戳（毫秒）转UTC日期时间

该方法是把13位毫秒级时间戳转为UTC日期时间DateTime，代码如下：

/// <summary>
/// 时间戳（毫秒）转UTC日期时间
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>UTC日期时间</returns>
public static DateTime ToUniversalTimeDateTimeByMilliseconds(this long timestamp)
{
    var dto = DateTimeOffset.FromUnixTimeMilliseconds(timestamp);
    return dto.ToUniversalTime().DateTime;
}

07
、时间戳（秒）转本地日期

该方法是把10位秒级时间戳转为本地日期DateOnly，代码如下：

/// <summary>
/// 时间戳（秒）转本地日期
/// </summary> 
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>本地日期</returns>
public static DateOnly ToLocalTimeDateBySeconds(this long timestamp)
{
    var dt = timestamp.ToLocalTimeDateTimeBySeconds();
    return DateOnly.FromDateTime(dt);
}

08
、时间戳（毫秒）转本地日期

该方法是把13位毫秒级时间戳转为本地日期DateOnly，代码如下：

/// <summary>
/// 时间戳（毫秒）转本地日期
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>本地日期</returns>
public static DateOnly ToLocalTimeDateByMilliseconds(this long timestamp)
{
    var dt = timestamp.ToLocalTimeDateTimeByMilliseconds();
    return DateOnly.FromDateTime(dt);
}

09
、时间戳（秒）转UTC日期

该方法是把10位秒级时间戳转为UTC日期DateOnly，代码如下：

/// <summary>
/// 时间戳（秒）转UTC日期
/// </summary> 
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>UTC日期</returns>
public static DateOnly ToUniversalTimeDateBySeconds(this long timestamp)
{
    var dt = timestamp.ToUniversalTimeDateTimeBySeconds();
    return DateOnly.FromDateTime(dt);
}

10
、时间戳（毫秒）转UTC日期

该方法是把13位毫秒级时间戳转为UTC日期DateOnly，代码如下：

/// <summary>
/// 时间戳（毫秒）转UTC日期
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>UTC日期</returns>
public static DateOnly ToUniversalTimeDateByMilliseconds(this long timestamp)
{
    var dt = timestamp.ToUniversalTimeDateTimeByMilliseconds();
    return DateOnly.FromDateTime(dt);
}

11
、时间戳（秒）转本地时间

该方法是把10位秒级时间戳转为本地时间TimeOnly，代码如下：

/// <summary>
/// 时间戳（秒）转本地时间
/// </summary> 
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>本地时间</returns>
public static TimeOnly ToLocalTimeTimeBySeconds(this long timestamp)
{
    var dt = timestamp.ToLocalTimeDateTimeBySeconds();
    return TimeOnly.FromDateTime(dt);
}

12
、时间戳（毫秒）转本地时间

该方法是把13位毫秒级时间戳转为本地时间TimeOnly，代码如下：

/// <summary>
/// 时间戳（毫秒）转本地时间
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>本地时间</returns>
public static TimeOnly ToLocalTimeTimeByMilliseconds(this long timestamp)
{
    var dt = timestamp.ToLocalTimeDateTimeByMilliseconds();
    return TimeOnly.FromDateTime(dt);
}

13
、时间戳（秒）转UTC时间

该方法是把10位秒级时间戳转为UTC时间TimeOnly，代码如下：

/// <summary>
/// 时间戳（秒）转UTC时间
/// </summary> 
/// <param name="timestamp">时间戳（秒）</param>
/// <returns>UTC时间</returns>
public static TimeOnly ToUniversalTimeTimeBySeconds(this long timestamp)
{
    var dt = timestamp.ToUniversalTimeDateTimeBySeconds();
    return TimeOnly.FromDateTime(dt);
}

14
、时间戳（毫秒）转UTC时间

该方法是把13位毫秒级时间戳转为UTC时间TimeOnly，代码如下：

/// <summary>
/// 时间戳（毫秒）转UTC时间
/// </summary> 
/// <param name="timestamp">时间戳（毫秒）</param>
/// <returns>UTC时间</returns>
public static TimeOnly ToUniversalTimeTimeByMilliseconds(this long timestamp)
{
    var dt = timestamp.ToUniversalTimeDateTimeByMilliseconds();
    return TimeOnly.FromDateTime(dt);
}

15
、字符串转日期时间，转换失败则返回空

该方法是把字符串转为日期时间DateTime，转换失败则返回空，具体代码如下：

/// <summary>
/// 字符串转日期时间，转换失败则返回空
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <returns>日期时间</returns>
public static DateTime? ToDateTime(this string source)
{
    if (DateTime.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return default;
}

16
、字符串转日期时间，转换失败则返回默认日期时间

该方法是把字符串转为日期时间DateTime，转换失败则返回默认日期时间，具体代码如下：

/// <summary>
/// 字符串转日期时间，转换失败则返回默认值
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <param name="dateTime">默认日期时间</param>
/// <returns>日期时间</returns>
public static DateTime ToDateTimeOrDefault(this string source, DateTime dateTime)
{
    if (DateTime.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return dateTime;
}

17
、字符串转日期，转换失败则返回空

该方法是把字符串转为日期DateOnly，转换失败则返回空，具体代码如下：

/// <summary>
/// 字符串转日期，转换失败则返回空
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <returns>日期</returns>
public static DateOnly? ToDateOnly(this string source)
{
    if (DateOnly.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return default;
}

18
、字符串转日期，转换失败则返回默认日期

该方法是把字符串转为日期DateOnly，转换失败则返回默日期，具体代码如下：

/// <summary>
/// 字符串转日期，转换失败则返回默认日期
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <param name="dateOnly">默认日期</param>
/// <returns>日期</returns>
public static DateOnly ToDateOnlyOrDefault(this string source, DateOnly dateOnly)
{
    if (DateOnly.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return dateOnly;
}

19
、字符串转时间，转换失败则返回空

该方法是把字符串转为日期TimeOnly，转换失败则返回空，具体代码如下：

/// <summary>
/// 字符串转时间，转换失败则返回空
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <returns>时间</returns>
public static TimeOnly? ToTimeOnly(this string source)
{
    if (TimeOnly.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return default;
}

20
、字符串转时间，转换失败则返回默认时间

该方法是把字符串转为日期TimeOnly，转换失败则返回默认时间，具体代码如下：

/// <summary>
/// 字符串转时间，转换失败则返回默认时间
/// </summary>
/// <param name="source">需转换的字符串</param>
/// <param name="timeOnly">默认时间</param>
/// <returns>时间</returns>
public static TimeOnly ToTimeOnlyOrDefault(this string source, TimeOnly timeOnly)
{
    if (TimeOnly.TryParse(source, CultureInfo.InvariantCulture, DateTimeStyles.None, out var date))
    {
        return date;
    }
    return timeOnly;
}

稍晚些时候我会把库上传至Nuget上，大家可以搜索Ideal.Core.Common直接使用。

注
：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。
https://gitee.com/hugogoos/Ideal

全网最适合入门的面向对象编程教程：58 Python 字符串与序列化-序列化 Web 对象的定义与实现

image

摘要：

如果我们要在不同的编程语言之间传递对象，就必须把对象序列化为标准格式，比如XML\YAML\JSON格式这种序列化Web对象。这种序列化Web对象容易与其他程序设计语言交互，可读性强，容易被传递给其它系统或客户端。

原文链接：

FreakStudio的博客

往期推荐：

学嵌入式的你，还不会面向对象？？！

全网最适合入门的面向对象编程教程：00 面向对象设计方法导论

全网最适合入门的面向对象编程教程：01 面向对象编程的基本概念

全网最适合入门的面向对象编程教程：02 类和对象的 Python 实现-使用 Python 创建类

全网最适合入门的面向对象编程教程：03 类和对象的 Python 实现-为自定义类添加属性

全网最适合入门的面向对象编程教程：04 类和对象的Python实现-为自定义类添加方法

全网最适合入门的面向对象编程教程：05 类和对象的Python实现-PyCharm代码标签

全网最适合入门的面向对象编程教程：06 类和对象的Python实现-自定义类的数据封装

全网最适合入门的面向对象编程教程：07 类和对象的Python实现-类型注解

全网最适合入门的面向对象编程教程：08 类和对象的Python实现-@property装饰器

全网最适合入门的面向对象编程教程：09 类和对象的Python实现-类之间的关系

全网最适合入门的面向对象编程教程：10 类和对象的Python实现-类的继承和里氏替换原则

全网最适合入门的面向对象编程教程：11 类和对象的Python实现-子类调用父类方法

全网最适合入门的面向对象编程教程：12 类和对象的Python实现-Python使用logging模块输出程序运行日志

全网最适合入门的面向对象编程教程：13 类和对象的Python实现-可视化阅读代码神器Sourcetrail的安装使用

全网最适合入门的面向对象编程教程：全网最适合入门的面向对象编程教程：14 类和对象的Python实现-类的静态方法和类方法

全网最适合入门的面向对象编程教程：15 类和对象的 Python 实现-__slots__魔法方法

全网最适合入门的面向对象编程教程：16 类和对象的Python实现-多态、方法重写与开闭原则

全网最适合入门的面向对象编程教程：17 类和对象的Python实现-鸭子类型与“file-like object“

全网最适合入门的面向对象编程教程：18 类和对象的Python实现-多重继承与PyQtGraph串口数据绘制曲线图

全网最适合入门的面向对象编程教程：19 类和对象的 Python 实现-使用 PyCharm 自动生成文件注释和函数注释

全网最适合入门的面向对象编程教程：20 类和对象的Python实现-组合关系的实现与CSV文件保存

全网最适合入门的面向对象编程教程：21 类和对象的Python实现-多文件的组织：模块module和包package

全网最适合入门的面向对象编程教程：22 类和对象的Python实现-异常和语法错误

全网最适合入门的面向对象编程教程：23 类和对象的Python实现-抛出异常

全网最适合入门的面向对象编程教程：24 类和对象的Python实现-异常的捕获与处理

全网最适合入门的面向对象编程教程：25 类和对象的Python实现-Python判断输入数据类型

全网最适合入门的面向对象编程教程：26 类和对象的Python实现-上下文管理器和with语句

全网最适合入门的面向对象编程教程：27 类和对象的Python实现-Python中异常层级与自定义异常类的实现

全网最适合入门的面向对象编程教程：28 类和对象的Python实现-Python编程原则、哲学和规范大汇总

全网最适合入门的面向对象编程教程：29 类和对象的Python实现-断言与防御性编程和help函数的使用

全网最适合入门的面向对象编程教程：30 Python的内置数据类型-object根类

全网最适合入门的面向对象编程教程：31 Python的内置数据类型-对象Object和类型Type

全网最适合入门的面向对象编程教程：32 Python的内置数据类型-类Class和实例Instance

全网最适合入门的面向对象编程教程：33 Python的内置数据类型-对象Object和类型Type的关系

全网最适合入门的面向对象编程教程：34 Python的内置数据类型-Python常用复合数据类型：元组和命名元组

全网最适合入门的面向对象编程教程：35 Python的内置数据类型-文档字符串和__doc__属性

全网最适合入门的面向对象编程教程：36 Python的内置数据类型-字典

全网最适合入门的面向对象编程教程：37 Python常用复合数据类型-列表和列表推导式

全网最适合入门的面向对象编程教程：38 Python常用复合数据类型-使用列表实现堆栈、队列和双端队列

全网最适合入门的面向对象编程教程：39 Python常用复合数据类型-集合

全网最适合入门的面向对象编程教程：40 Python常用复合数据类型-枚举和enum模块的使用

全网最适合入门的面向对象编程教程：41 Python常用复合数据类型-队列（FIFO、LIFO、优先级队列、双端队列和环形队列）

全网最适合入门的面向对象编程教程：42 Python常用复合数据类型-collections容器数据类型

全网最适合入门的面向对象编程教程：43 Python常用复合数据类型-扩展内置数据类型

全网最适合入门的面向对象编程教程：44 Python内置函数与魔法方法-重写内置类型的魔法方法

全网最适合入门的面向对象编程教程：45 Python实现常见数据结构-链表、树、哈希表、图和堆

全网最适合入门的面向对象编程教程：46 Python函数方法与接口-函数与事件驱动框架

全网最适合入门的面向对象编程教程：47 Python函数方法与接口-回调函数Callback

全网最适合入门的面向对象编程教程：48 Python函数方法与接口-位置参数、默认参数、可变参数和关键字参数

全网最适合入门的面向对象编程教程：49 Python函数方法与接口-函数与方法的区别和lamda匿名函数

全网最适合入门的面向对象编程教程：50 Python函数方法与接口-接口和抽象基类

全网最适合入门的面向对象编程教程：51 Python函数方法与接口-使用Zope实现接口

全网最适合入门的面向对象编程教程：52 Python函数方法与接口-Protocol协议与接口

全网最适合入门的面向对象编程教程：53 Python字符串与序列化-字符串与字符编码

全网最适合入门的面向对象编程教程：54 Python字符串与序列化-字符串格式化与format方法

全网最适合入门的面向对象编程教程：55 Python字符串与序列化-字节序列类型和可变字节字符串

全网最适合入门的面向对象编程教程：56 Python字符串与序列化-正则表达式和re模块应用

全网最适合入门的面向对象编程教程：57 Python字符串与序列化-序列化与反序列化

更多精彩内容可看：

给你的 Python 加加速：一文速通 Python 并行计算

一文搞懂 CM3 单片机调试原理

肝了半个月，嵌入式技术栈大汇总出炉

电子计算机类比赛的“武林秘籍”

一个MicroPython的开源项目集锦：awesome-micropython，包含各个方面的Micropython工具库

Avnet ZUBoard 1CG开发板—深度学习新选择

SenseCraft 部署模型到Grove Vision AI V2图像处理模块

文档和代码获取：

可访问如下链接进行对文档下载：

https://github.com/leezisheng/Doc

image

本文档主要介绍如何使用 Python 进行面向对象编程，需要读者对 Python 语法和单片机开发具有基本了解。相比其他讲解 Python 面向对象编程的博客或书籍而言，本文档更加详细、侧重于嵌入式上位机应用，以上位机和下位机的常见串口数据收发、数据处理、动态图绘制等为应用实例，同时使用 Sourcetrail 代码软件对代码进行可视化阅读便于读者理解。

相关示例代码获取链接如下：
https://github.com/leezisheng/Python-OOP-Demo

正文

序列化 Web 对象

如果我们要在不同的编程语言之间传递对象，就必须把对象序列化为标准格式，比如 XML\YAML\JSON 格式这种序列化 Web 对象。这种序列化 Web 对象容易与其他程序设计语言交互，可读性强，容易被传递给其它系统或客户端。

在 Python 最常用的序列化 Web 对象就是环境配置的 yaml 文件，anaconda 可以管理不同的环境配置，当我们想将自己的环境配置分享给其他人时，就可以生成 yaml 文件，这样别人可以快速导入 yaml 文件构建和我们一样的环境来运行代码。

我们可以在命令行中使用如下指令生成 yaml 文件：

conda env export > environment.yml

image

使用 JSON 实现序列化 Web 对象

JavaScript Object Notation（JSON）是一种人类可读的格式，用于存储基础数据类型。JSON 是一种标准格式，可以被各式各样的客户端系统解析。因此，JSON 非常适合用于在完全不同的系统之间进行数据传输。而且，JSON 不支持任何可执行代码，只有数据可以被序列化；因此，更难向其中植入恶意代码。JSON 格式因其易于被 JavaScript 引擎解析的特性，常被用于 Web 服务器与具备 JavaScript 功能的浏览器间的数据传输。若 Web 应用的服务器端采用 Python 编写，为确保数据的兼容性与通用性，需将内部数据转换为 JSON 格式。

我们可以使用 Python 中的 json 模块生成 JSON 文件，该模块与 pickle 类似，也提供了 dumps()、dump()、loads()、load()四个函数，但输出结果是 JSON 格式的。此外，
json 函数作用于 str 对象，而不是 bytes。因此，当输出或载入时，我们需要创建文本模式的文件而不是二进制模式。
JSON 只能序列化基本类型，如整数、浮点数和字符串，以及简单的容器，如字典和列表。这些都直接映射到 JSON 形式，不过** JSON 不能表示类、方法或函数。不能用这种格式来传输完整的对象。因为接收者通常不是 Python 对象，接收者不能与 Python 以同样的方式来理解类或方法。**

image

image

image

image

import json

_# 人员信息列表_
humaninfodic={
    'age'   : 18,
    'name'  : True,
    'gender': 10,
    'email' : 11.1,
}

_# 序列化到文件中_
with open('test.json', 'w') as fp:
    json.dump(humaninfodic, fp, indent=4)

_# 反序列化文件中的内容_
with open('test.json', 'r') as fp:
    dic = json.load(fp)
    print(dic)

运行结果如下：

image

image

这里，需要注意的是，Python 中字典的非字符的值 Key 被转换成 JSON 字符串时都会被转换为小写字符串，例如 True 会被映射为 true，False 被映射为 false，而 None 会被映射为 null；同时 Python 中的元组在序列化时会被转换为 array 类型，但是反序列化时，array 类型会被转化为 Python 中的列表类型。

JSON 和 Python 内置的数据类型对应如下：

JSON 类型 Python 类型
{} dict
[] list
"string" str
1234.56 int 或 float
true/false True/False
null None

如果想要序列化的对象只有数据，我们可以直接序列化对象的__dict__属性。或者我们也可以针对特定的对象，通过自定义代码来创建或解析 JSON 序列化字典。

image

image

在 json 模块中，对象的存储和载入功能均设有一个可选参数，用以执行特定的自定义操作。具体来说，
dump
和
dumps
方法接受一个名为
cls
（即“class”的简写，因其为 Python 的保留关键字）的关键字参数。
当传递此参数时，它必须是
JSONEncoder
的一个子类，并且要求重写了
default
方法。
这个方法的设计初衷是接收任意类型的对象作为参数，然后将其转换为 json 能够处理的字典类型。
如果在处理过程中遇到不知道如何处理的对象类型，可以通过调用
super()
方法，使得该对象能够按照正常的方式进行序列化处理，即按照基本类型进行序列化。

同样地，
load
和
loads
方法也接受一个名为
cls
的参数，它是
JSONDecoder
的一个子类。通常情况下，通过
object_hook
关键字传递一个函数便足够了。
这个函数的任务是接收一个字典作为参数，并返回一个对象。如果在处理过程中遇到不知道如何处理的字典，可以选择不进行任何修改，直接将其返回。这种设计使得用户在进行 json 数据的解析时，能够更加灵活和方便地处理各种复杂的数据类型。

import json

_# 定义联系人类_
class Contact:
    def __init__(self, first, last):
        _# 属性1，first name是名字_
        self.first = first
        _# 属性2，last name是姓氏_
        self.last = last
    @property
    def full_name(self):
        return("{} {}".format(self.first, self.last))

_# 自定义序列化编码器类_
class ContactEncoder(json.JSONEncoder):
    _# default 方法检查了我们想要序列化的对象类型_
    def default(self, obj):
        _# 如果是联系人类，我们手动将其转换为字典_
        if isinstance(obj, Contact):
            return {
                    _# 传递了一个额外的属性来说明这是一个联系人对象_
                    _# 因为没有其他办法可以在载入之后知道它的类型_
                    'is_contact': True,
                    'first': obj.first,
                    'last': obj.last,
                    'full': obj.full_name}
        _# 否则，让其父类来处理序列化（假设它是基本类型，json 知道如何处理）_
        return super().default(obj)

_# 定义一个JSON文件解码器函数_
def decode_contact(dic):
    _# 写一个函数接受字典为参数_
    _# 检查是否包含 is_contact 变量来决定是否将其转换为联系人_
    if dic.get('is_contact'):
        return Contact(dic['first'], dic['last'])
    else:
        return dic

if __name__ == '__main__':
    c = Contact("John", "Smith")
    data = json.dumps(c, cls=ContactEncoder)
    print(data)
    c = json.loads(data, object_hook=decode_contact)
    print(c.full_name)

运行结果如下：

image

使用 XML 实现序列化 Web 对象

在当今的软件开发领域，
XML 作为一种灵活且强大的标记语言，已经广泛应用于数据存储、配置管理、网络传输等多个场景。
它的可扩展性和自描述性让它成为了不同系统和平台之间数据交换的理想格式。

XML 指可扩展标记语言（eXtensible Markup Language），是一套定义语义标记的规则
，这些标记将文档分成许多部件并对这些部件加以标识，
它被设计用来传输和存储数据，不用于表现和展示数据。
它也是
元标记语言，即定义了用于定义其他与特定领域有关的、语义的、结构化的标记语言的句法语言。

如下我们列举了一个 xml 文件的例子：

<?xml version="1.0" encoding="utf-8"?>
<catalog>
    <maxid>4</maxid>
    <login username="pytest" passwd='123456'>
        <caption>Python</caption>
        <item id="4">
            <caption>测试</caption>
        </item>
    </login>
    <item id="2">
        <caption>Zope</caption>
    </item>
</catalog>

以上 XML 格式的文件中，包含了一个名为"catalog"的根元素。根元素下有一个名为"maxid"的子元素，其值为"4"。接着是一个名为"login"的子元素，它包含两个子元素：一个名为"caption"的子元素，其值为"Python";另一个名为"item"的子元素，其 id 属性值为"4",包含一个名为"caption"的子元素，其值为"测试"。最后还有一个名为"item"的子元素，其 id 属性值为"2",包含一个名为"caption"的子元素，其值为"Zope"。

其中书名号圈住的部分“
”为标签，标签必须成对出现，有开始标签就需要有结束标签，例如” “为开始标签，“ ”为结束标签。

一个基本的 XML 文档结构包括以下部分：

结构部分 作用
声明部分 位于文档的最开始，声明 XML 的版本和编码方式。例如：。
根元素 每个 XML 文档都有一个根元素，它包含了所有其他元素。
子元素 根元素内部可以包含多个子元素，子元素可以嵌套并形成树状结构。
属性 元素可以有属性，属性提供了关于元素的额外信息。
文本内容 元素可以包含文本内容。

Python 作为一门简洁而强大的编程语言，提供了丰富的库来处理 XML 数据，使得从解析到修改再到创建 XML 文档变得既简单又高效。Python 有三种方法解析 XML、SAX、DOM，以及 ElementTree。

image

其中，xml.etree.ElementTree（简称 ET）提供了一个轻量级的 Pythonic 方式来处理 XML 数据。ET 允许用户轻松地读取、修改和创建 XML 文件。由于是标准库的一部分，因此不需要额外安装即可使用，这使得它成为处理 XML 数据的一个便捷选择。

对于 ElementTree 库来说，常见使用操作包括解析 XML 文档，获取根元素、遍历子元素、读取元素的标签、文本和属性，以及如何根据需要获取或删除特定元素，以及保存修改后的 XML 文档。

这里，对于 XML 文件仅作为了解使用，并不展开进行讲解。

使用 YAML 实现序列化 Web 对象

XML 文件虽然功能强大，但由于其标记语言的特性，通常不太易于阅读。相反，XML 在需要对验证、架构和名称空间进行精细控制的复杂项目中表现出色。
与 XML 相比，YAML 则专注于数据格式化，以可读代码的形式呈现，其内联风格与 JSON 颇为相似。YAML 旨在提供更为直观和易读的数据表示方式，以满足不同场景下的需求。

YAML，作为一种高度人性化的数据序列化语言，能够与当前主流的编程语言无缝集成。其名称“YAML”来源于“YAML Ain't a Markup Language”（YAML 不是一种标记语言）的递归缩写，这一命名既体现了其独特性，又突显了其与众不同的设计理念。

YAML 的语法结构与其他高级语言相似，能够轻松表达清单、散列表以及标量等多种数据形态。它巧妙地利用空白符号进行缩进，并大量依赖外观特征来展示数据结构的层次关系。
这种设计使得 YAML 特别适合用于编辑数据结构、编写各种配置文件、打印调试信息以及呈现文件大纲等场景。

此外，YAML 配置文件通常以“.yml”作为文件后缀，这一命名约定有助于用户快速识别和管理 YAML 文件。

它的基本语法规则如下：

（1）大小写敏感；

（2）使用缩进表示层级关系；

（3）缩进时不允许使用 Tab 键，只允许使用空格。

（4）缩进的空格数目不重要，只要相同层级的元素左侧对齐即可

YAML 支持的数据结构有三种：

（1）对象：键值对的集合，又称为映射（mapping）/ 哈希（hashes） / 字典（dictionary）；

（2）数组：一组按次序排列的值，又称为序列（sequence） / 列表（list）；

（3）纯量（scalars）：单个的、不可再分的值。

在 Python 中，有多个库可用于解析和生成 YAML 数据，其中最常用的是 PyYAML。

image

这里，我们以下列名为 config.yaml 的 YAML 配置文件为例，简单讲解一下 YAML 文件语法：

_# 配置文件示例_
  
_# 服务器配置_
server:  
  host: localhost  
  port: 8080  

_# 数据库配置_
database:  
  type: MySQL  
  host: 127.0.0.1  
  port: 3306  
  username: root  
  password: password  

_# 日志记录_
logging:  
  level: info  
  file: app.log

_# 应用配置_
app:
  debug: true
  log_level: info

这里，该文件使用井号(#)表示注释，使用缩进表示层级关系，并且使用冒号(:)分隔键和值。

这个 YAML 文件包含以下几个部分：

（1）服务器配置：包括主机名和端口号；

（2）数据库配置：包括数据库类型、主机名、端口号、用户名和密码；

（3）日志记录：包括日志级别和日志文件路径；

（4）应用配置：包括是否开启调试模式和日志级别。

XML 和 YAML 文件都有一些复杂的特征，如果被恶意利用，就可以允许在主机上执行任意命令。
这与 JSON 文件不同，JSON 不支持任何可执行代码，只有数据可以被序列化。

image

  1. 1
  2. ...
  3. 52
  4. 53
  5. 54
  6. 55
  7. 56
  8. 57
  9. 58
  10. ...
  11. 75