2024年11月

本篇准备开始介绍
Streamlit
的组件。

Streamlit
的组件非常多,后续几篇打算按照用途的分类,介绍每个分类中最常用的组件。

本次从最简单的组件开始,介绍文本和标题相关的组件,也就是以下4个组件:

  1. st.text
    :用于显示普通的文本内容
  2. st.title
    :用于显示页面的大标题
  3. st.header
    :用于显示一级标题
  4. st.subheader
    :用于显示二级标题

1. st.text 组件

st.text

Streamlit
中最基本的文本展示组件。

它的主要功能是显示普通的文本内容,没有特殊的格式或样式,

主要用于展示段落、说明性文字或任何不需要特殊强调的文本。

使用场景主要包括:

  • 展示应用程序的说明文字
  • 显示用户输入或动态生成的文本内容
  • 作为其他组件之间的过渡文本

st.text
既可以显示
单行文本
,也可以通过
三引号
来显示
多行文本

import streamlit as st

st.text("这是一个使用 st.text 显示的普通文本。")
st.text(
    """这是一个使用 st.text 显示的多行文本。
每一行都会单独显示,
并且保持原有的格式。"""
)

2. st.title 组件

st.title
是用于显示页面大标题的组件。

它的字体大且加粗,非常醒目,通常位于页面的顶部或重要内容的开头。

st.title
的主要作用是吸引用户的注意力,明确应用程序的主题或当前部分的核心内容。

它的使用场景有:

  • 作为整个应用程序的标题
  • 标识应用程序中的重要部分或章节
  • 在页面顶部提供清晰的导航指示

st.title
使用非常简单。

st.title("XXX数据应用程序")

3. st.header 组件

st.header
是用于显示一级标题的组件。

它的字体和加粗程度略小于
st.title
,但仍然足够显眼,能够清晰地标识出页面内容的不同部分。

st.header
的主要作用是帮助用户理解应用程序的结构,快速定位到感兴趣的内容部分。

st.header
可以当成
HTML
中的
H1
标签来看,它的使用场景主要有:

  • 划分应用程序的不同区块或章节
  • 为特定部分的内容提供标题
  • 在长页面中提供视觉上的分隔

st.header
的使用和
st.title
类似,下面的示例把它当作内容分割的标题。

import streamlit as st
 
st.header("引言")
st.text("本文介绍了 Streamlit 的基本文本展示组件。")
 
st.header("方法")
st.text("我们采用了多种方法来分析数据。")
 
st.header("结果")
st.text("以下是我们的分析结果。")

4. st.subheader 组件

st.subheader
是用于显示二级标题的组件。

相对于
st.header
,它的字体和加粗程度进一步减小,但仍然能够清晰地标识出内容的子部分。

st.subheader
的主要作用是进一步细化内容结构,为用户提供更详细的导航或内容概述,可以把它当成
HTML
中的
H2
标签来看。

它的使用场景:

  • 在一级标题下进一步划分内容子部分
  • 为特定的小节或段落提供标题
  • 在需要强调但不需要过分突出的地方使用

下面的示例展示二级标题的使用:

st.header("销售数据分析")
st.subheader("月度销售趋势")
st.text("这里将展示每月的销售数据趋势。")

st.subheader("年度销售趋势")
st.text("这里将展示整年的销售数据趋势。")
 
st.subheader("产品类别销售情况")
st.text("接下来,我们将分析不同产品类别的销售情况。")

5. 总结

上面介绍的4个组件
st.text

st.title

st.header

st.subheader
并不是孤立存在的,它们通常会被组合在一起使用,以构建出具有层次感和逻辑性的页面布局。

使用时,根据内容层次选择组件,比如,

使用
st.title
作为整个页面或应用程序的开头,明确主题和核心目的;

使用
st.header
来划分页面的主要部分或章节,每个
st.header
都应该代表一个相对独立且完整的内容区块;


st.header
之下,使用
st.subheader
来进一步细化内容,为具体的小节或段落提供标题;

最后,用
st.text
来填充上述标题之间的空白,提供具体的描述、解释或补充信息。

需要
注意
的是,虽然这些文本展示组件非常有用,但也要避免过度使用,过多的标题和文本可能会让用户感到混乱和迷失方向。

因此,在使用这些组件时,要确保它们真正为页面增加了价值,而不是成为冗余的信息。

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