查看“︁X-Y”︁的源代码

X-Y 序列是由国内的大数研究者 Go men 于 2023 年提出的记号，是一个 Y 序列的强大扩展。X-Y 序列一共有两个版本，下面我们介绍第二版的展开规则。

=== 定义 ===
'''作山脉图'''

山脉图是一个“二维数组”，待展开数列依次置于山脉图第 [0] 行，首项放在第 1 列，后面各项依次放在第 2、3、4... 列，每一项称为山脉图的“元素”，如果待展开数列的元素的父元素未指定，则该元素前方最近的小于该元素的元素是该元素的父元素；值大于 1 的元素与其父元素作差，差作为新元素加入山脉图中，新元素所在列与该元素相同，新元素的行这样确定：满足新元素与该元素行差等于新元素与该元素父元素行差的最小行；新元素叫做该元素的“足元素”（foot），相应地，该元素是新元素的“头元素”（head，ω-Y 的叫法是“右腿”），该元素的父元素是新元素的“左腿”（沿用 ω-Y 的称谓）；新产生的元素，若其值大于 1，则需要确定它的父元素，新元素的左腿如果没有足元素或足元素行标大于新元素，则左腿是新元素的待定父元素，否则左腿的足元素是新元素的待定父元素；如果待定父元素的值小于新元素，待定父元素就是新元素的父元素，否则待定父元素的父元素是新元素的待定父元素，然后循环判断待定父元素，直到确定父元素为止；当山脉图不能产生新元素时（山脉图各列最大行元素值均为 1 时），作图完成。

行标：行标用数列来表示，如首行行标为 [0]，[0] 就是一个只有一项的数列；

维度：行标数列的长度称作“维度”（除 [0] 外，行标数列的首项不能为 0，若为 0 需将其去掉，如 [0,0,1,2,3] 应写成 [1,2,3]，该行标的维度为 3）；

维度等级：维度为 1 的行标都是同一等级；维度大于 1 的行标，行标数列的首项值就是该行标的维度等级；

维度等级差：两个同维度行标数列首项之差；

行偏差：维度大于 1 的行标，去掉首项后的新数列即为原行标对于其所在维度等级的行偏差（如果新数列首项为 0，则应将 0 去掉，例如 [2,0,0,3,5] 对于其所在第 5 维度第 2 维度等级的行偏差为 [3,5]）；

行标大小比较：维度更高的行标数列大于维度更低的行标数列；维度相同的行标数列比较大小，从首项开始依次往后比较各项的值，先遇到值更大的项的行标更大；如果两个行标维度相同，且各项的值对应相等，则这两个行标相等；

行标相加：设 α 与 β 是两个行标数列，若 α 的维度小于 β 的维度，则有 α + β = β（行标数列加法不具有交换律，β + α 并不等于 α + β）；若 α 的维度等于 β 的维度，则 α + β 的首项等于 α 的首项与 β 的首项之和，其余各项与 β 对应项相等，如 [1,4,5] + [3,2,1] = [4,2,1]；若 α 的维度大于 β 的维度，则取从 α 末尾提取长度与 β 相同的子数列，与 β 相加后取代 α 原来的子数列，新得的数列即 α + β，如 [1,2,3,4,5] + [3,2,1] = [1,2,6,2,1]；

行差：两个行标之差，简称为行差 (一般是用较大的行标减较小的行标)，若 α 的维度大于 β 的维度，有 α − β = α；若 α 的维度等于 β 的维度且 α > β，从首项起依次比较 α 和 β 各项，直到遇到第一个不相等的项，α−β 的首项为 α 的该项减 β 的对应项，其余项为 α 中该项后边的项，如 [2,3,4,2,1] - [2,3,3,4,5] = [4,2,1] - [3,4,5] = [1,2,1]；可知若 α + γ = β，则 β − α = γ；若 α = β，则 α − β = [0]；第 [0] 行元素与第 [0] 行元素作差，差必定在第 [1] 行，第 [1] 行元素与第 [0] 行元素作差，差必定在第 [1,0] 行，因为 [1,0] 是满足 α − [1] = α − [0] 的最小行标；一般地，若某元素行标为 β（β 大于 [0]），其父元素行标为 α，令 γ = β − α，若 γ 维度为 k，令 δ = [1,0,0,...]，其中 δ 首项是 1，其余项均为 0，维度为 k + 1，则 δ 是满足 β + δ = α + δ 的最小行标，即 β + δ 或 α + δ 即是新元素的行标；[0] 行是第 1 维度的维度起点，此外，首项是 1，其余各项均为 1 的行是其所在维度的起点，[1,0] 行、[1,0,0] 行分别是 2、3 维的维度起点，等等；

'''确定根元素'''

芽元素：山脉图最右列行标第 2 大的元素叫做芽元素；

参照元素：若元素与其父元素在同一行，则父元素是该元素的参照元素，否则如果该元素不在首行，则该元素的左腿是该元素的参照元素，首行值为 1 的元素没有参照元素；

参照链：从某元素开始，顺着它的参照元素、参照元素的参照元素、参照元素的参照元素的参照元素... 溯源而上，直到某个没有参照元素的元素为止，这条链路叫做该元素的参照链；

根链：芽元素的参照链叫做根链；

准父元素：非首行值为 1 的元素，它的参照链中离它最近的值为 1 的元素，是该元素的准父元素；

主维度数列：提取根链中各元素的维度值组成一个数列，并将该数列末项（芽元素维度值）的值 +1，该数列即原数列的主维度数列；

根元素：如果芽元素与其父元素在同一维度，则芽元素的父元素是根元素；否则主维度数列（它也是一个 X − Y 数列）的根列对应的根链元素是根元素；根元素所在的列叫做根列，位于根列的元素叫作根列元素；

坏区：山脉图根列右边（不含根列）的区域叫做坏区；

元素编号：根列之前的元素编号均为 0，根列元素从上到下（上表示行标更小，下表示行标更大，下同）依次编号为 1,2,3,4,...，坏区元素编号等于其参考元素编号；

'''元素复制'''

去掉山脉图最右列行标最大的元素，最右列其它元素值减 1，如果根元素值大于 1（此时山脉图最右列最大行元素是减 1 后的芽元素，其值等于根元素），芽元素要以根元素的父元素为父元素继续作差，直到山脉图最右列最大行元素值为 1 时为止；

坏区长度：芽元素与根元素的列标之差就是坏区长度，用 L 表示；

元素每一轮复制要从左到右依次复制坏区的每一列，复制某一列元素时要从上往下依次复制该列的每一个元素，当该列元素都复制到目标位置之后，从下往上（最下方元素的值为 1）计算复制列中每一个元素的值；

复制元素的编号：复制元素的编号等于被复制元素的编号；

复制元素的列标：第 n 轮复制，复制元素的列标等于 被复制元素列标 + L × n（下文出现的 n 同样表示第 n 轮复制）；

复制元素的父元素：如果被复制元素的父元素（若被复制元素不在首行且值为 1，则认为该元素的准父元素为父元素）在根列之前，复制元素以被复制元素的父元素为父元素；如果被复制元素的父元素在根列或根列之后，复制元素与父元素的列差，应等于被复制元素与父元素的列差，复制元素的父元素所在列中行标小于等于复制元素的、行标最大的元素就是复制元素的父元素；

最大复制行参照元素：编号大于 0 的元素在第 n 轮复制时，第 根列 + L × n 列中编号与被复制元素相同的行标最大的元素是该元素的最大复制行参照元素；

最大复制行：元素在某一轮复制中可以复制到的最大行叫作该元素的最大复制行；(1) 如果被复制元素的编号为 0，则该元素的最大复制行与被复制元素的行相同；(2) 如果被复制元素编号大于 0 且不等于根元素编号，或被复制元素编号等于根元素编号且被复制元素与根元素的维度及维度等级相同，则被复制元素的最大复制行与最大复制行参照元素的行差，应等于被复制元素与根列同编号元素的行差；(3) 如果被复制元素编号等于根元素编号，且被复制元素维度等于根元素维度但被复制元素维度等级大于根元素维度等级，则被复制元素的最大复制行与最大复制行参照元素的维度等级差应等于被复制元素与根元素的维度等级差，且被复制元素的最大复制行的行偏差与被复制元素的行偏差相等；(4) 如果被复制元素编号等于根元素编号，且被复制元素维度大于根元素维度，则被复制元素的最大复制行的维度等于被复制元素的维度数列展开式中对应项的值，且被复制元素的最大复制行的维度等级和行偏差都与被复制元素相等；

元素的特征维度数列：编号等于根元素编号且维度大于根元素维度的元素都对应一个它自己的特征维度数列，一般简称为元素的维度数列；将元素参照链中维度大于根元素维度的项的维度提取出来，插入到主维度数列中根元素之后（插入项不影响原主维度数列各项的父子关系），新插入的项的父元素仍是前方最近的值比它小的元素，该数列就是该元素的特征维度数列（元素的维度数列也是 X-Y 数列），该元素对应特征维度数列中它的维度值那一项；

最小复制行：第 [0] 行元素的最小复制行是第 [0] 行，非 [0] 行元素的最小复制行由它的头元素在同一轮复制中的最大复制行与其父元素所在行作差生成（即如果元素 A 是元素 B 的足元素，则元素 A 的最小复制行元素是元素 B 的最大复制行元素的足元素）；

对元素的复制是从复制到最小复制行开始，即某轮对元素进行第 1 次复制时，必定将该元素复制到该轮最小复制行；当被复制元素复制出一个新元素之后，执行下述流程：(1) 判断新元素的足元素所在行与被复制元素最大复制行的大小；(2) 如果新元素的足元素所在行小于等于被复制元素的最大复制行，将被复制元素复制到足元素所在行，回到流程 1，否则执行流程 3；(3) 本轮对该元素的复制完成；如果元素下方有元素，对该元素复制完成后继续复制下方元素，否则该列元素复制完成。

==== 展开实例 ====
例如，X-Y(1'','' 3'','' 12'','' 60'','' 12) 的山脉图如表所示，最左侧一列为行标。上述 X-Y 序列展开的结果为

X-Y(1'','' 3'','' 12'','' 60'','' 12) = X-Y(1'','' 3'','' 12'','' 60'','' 11'','' 53'','' 354'','' 52'','' 333'','' 3035'','' 332'','' 2984'','' 39216'','' 2983'', ...'')''.''
{| class="wikitable"
|-
|'''0'''
|1
|3
|12
|60
|12
|-
|'''1'''
|
|2
|9
|48
|9
|-
|'''2'''
|
|
|7
|39
|7
|-
|'''3'''
|
|
|
|32
|
|-
|'''1,0'''
|
|1
|5
|25
|5
|-
|'''1,1'''
|
|
|4
|20
|4
|-
|'''1,2'''
|
|
|
|16
|
|-
|'''2,0'''
|
|
|3
|12
|3
|-
|'''2,1'''
|
|
|
|9
|
|-
|'''3,0'''
|
|
|
|6
|
|-
|'''1,0,0'''
|
|
|2
|3
|2
|-
|'''1,0,1'''
|
|
|
|1
|
|-
|'''1,0,0,0'''
|
|
|1
|
|1
|}
需要注意的是，上述展开规则的时间复杂度和空间复杂度是比较高的。因此对于较大的序列来说，其展开过程将是不能够在可承受的范围内完成的。对于此前的记号来说，通常只是其最终的取值大得不可承受。但是自 X-Y 序列开始，连一步的展开也逐渐开始变得不可能了。这或许意味着这条路已经走到了尽头，我们需要更加强大的记号核心才能够继续前进。

{{默认排序:个人记号}}
[[分类:记号]]