LOGI - 算法

Proof of Lucas' theorem

LOGI — Fri, 22 Dec 2023 11:30:00 +0000

The Theorem

对于非负整数 $n, m$ 和质数 $p$，有

$$ C_{n}^{m} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_0}^{m_0} \pmod p \tag{1} $$

其中，

$$ \begin{eqnarray} n = n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0 \tag{2} \\\ m = m_kp^k + m_{k - 1}p^{k - 1} + \cdots + m_1p + m_0 \tag{3} \end{eqnarray} $$

分别是 $n,m$ 的 $p$ 进制展开，$k$ 为非负整数，$0 \le n_i, m_i \le p - 1$。

Inference

由式 $(2), (3)$ 得

$$ \begin{eqnarray} n \bmod p = n_0 \tag{4} \\\ m \bmod p = m_0 \tag{5} \\\ \lfloor \frac{n}{p} \rfloor = n_kp^{k - 1} + n_{k - 1}p^{k - 2} + \cdots + n_1 \tag{6} \\\ \lfloor \frac{m}{p} \rfloor = m_kp^{k - 1} + m_{k - 1}p^{k - 2} + \cdots + m_1 \tag{7} \end{eqnarray} $$

将定理运用到式 $(6), (7)$ 上，有

$$ C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} \pmod p \tag{8} $$

将式 $(4), (5), (8)$ 代入式 $(1)$ 得

$$ C_{n}^{m} \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} C_{n \bmod p}^{m \bmod p} \pmod p \tag{9} $$

The Proof

对于质数 $p$ 和整数 $k$，当 $1 \le k \le p - 1$ 时，有

$$ C_{p}^{k} = \frac{p \cdot (p - 1) \cdots (p - k + 1)}{k \cdot (k - 1) \cdots 1} \tag{10} $$

由于分母的每一项都与 $p$ 互质，因此 $C_{p}^{k} \bmod p = 0$。进而

$$ \begin{array} \left (1 + X)^p & = C_p^0 + C_p^1X + C_p^2X^2 + \cdots + C_p^{p - 1}X^{p - 1} + C_p^pX^p \\\ & \equiv 1 + X^p \pmod p \tag{11} \end{array} $$

下面用数学归纳法证明 $(1 + X)^{p^i} \equiv 1 + X^{p^i} \pmod p$ 对于任意正整数 $i$ 都成立。

已证 $i = 1$ 时，上式成立。
假设当 $i = k$ 时，上式成立，则当 $i = k + 1$ 时，
$$ \begin{array} \left (1 + X)^{p^{k + 1}} &= [(1 + X)^{p^k}]^p \\\ &\equiv (1 + X^{p^k})^p \pmod p,\ 令 X^\prime = X^{p^k}，运用式 (11) \\\ &\equiv 1 + (X^{p^k})^p \pmod p \\\ &\equiv 1 + X^{p^{k + 1}} \pmod p \tag{12} \end{array} $$

由此得证。进而

$$ \begin{array} \left (1 + X)^n & = (1 + X)^{n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0} \\\ & = (1 + X)^{n_kp^k} \cdot (1 + X)^{n_{k - 1}p^{k - 1}} \cdots (1 + X)^{n_{1}p} \cdot (1 + X)^{n_{0}} \\\ & \equiv (1 + X^{p^k})^{n_k} \cdot (1 + X^{p^{k - 1}})^{n_{k - 1}} \cdots (1 + X^p)^{n_{1}} \cdot (1 + X)^{n_{0}} \bmod p \tag{13} \end{array} $$

式 $(13)$ 的左边 $X^m$ 的系数为 $C_n^m$，结合式 $(3)$ 可验证右边 $X^m$ 的系数为

$$ C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} C_{n_0}^{m_0} \tag{14} $$

由于左右两边系数一定相等，因此式 $(1)$ 成立。显然，当 $n < m$ 时，必存在 $n_i < m_i$，此时左右两边系数都为 $0$，等式仍然成立。

Implementation of Variable Layer Loops and a Generalized Method for Recursive to Non-Recursive Conversion

LOGI — Wed, 16 Aug 2023 10:23:00 +0000

Problem

平常我们最多只写 3 重循环，比如：

for (let i = 0; i < 3; i++)
  for (let j = 0; j < 3; j++)
    for (let k = 0; k < 3; k++)
      console.log(i, j, k);

以上代码输出如下：

每层循环对应一条 for 语句，这种硬编码方式无法应对循环层数可变的情况。备用解决方案是动态生成源码文本，创建编译或解释器进程执行，但这肯定不是我们想要的。

[...]

Bindian Signalizing

LOGI — Sat, 07 May 2022 10:50:00 +0000

这是 2010 年 Codeforces Beta Round #5 中的 E 题，曾在 2017 年京东笔试中出现，转载本题解请注明出处

[...]

Reverse a Stack Only with Recursion and That Stack

LOGI — Sun, 01 May 2022 11:50:00 +0000

只用递归和自身反转栈，这题机试没法考，面试考纯属刁难，当作回溯练习食用最佳。

[...]

Sequential Nim

LOGI — Sun, 03 Apr 2022 09:48:00 +0000

题目翻译

原题链接

有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。两人轮流取石子，每次只能取编号最小且有石子的堆。每次可在一堆石子中取走若干个（至少取 $1$ 个），当一个人没有石子可取时，他就输了。

现在给出每堆石子的数量，假设两人都采取最优策略，问最后是先手 (First) 胜利还是后手 (Second) 胜利。

最优解

考虑几种特殊情形

只有一堆，先手直接取完获胜
只有两堆，并且第一堆石子数 $a_1 > 1$，先手可取 $a_1 - 1$ 个，后手只能取剩下一个，先手再把第二堆直接取完获胜。这种策略可应用于 $a_1,a_2,...,a_{n-1} > 1$
只有两堆，并且 $a_1 = 1$，先手只能取完第一堆，后手直接取完第二堆获胜。推广到 $a_1, a_2, ..., a_{n-1} = 1$，此时先手没有主动权，输赢由石子数为 $1$ 的前缀堆数决定，偶数个先手赢，奇数个后手赢
如果所有堆都只有一颗石子，输赢由石子堆数决定，偶数堆后手赢，奇数堆先手赢

考虑一般情形

$$ \underbrace{1, 1, ..., 1}_{k_0},\ \overbrace{a_{k_0+1},a_{k_0+2},...,a_{k_0+x_0}}^{x_0},\ \underbrace{ \underbrace{1, 1, ..., 1}_{k_1},\ \overbrace{a_{k_0+x_0+k_1+1},a_{k_0+x_0+k_1+2},...,a_{k_0+x_0+k_1+x_1}}^{x_1},\ ..., }_{repeat} a_n $$

其中未标 $1$ 的石子堆数大于 $1$

由特殊情形 $2, 3$ 的分析可知，如果中间没有 $1$，$k_0$ 决定输赢
如果中间有 $1$，不妨假设先手首先取 $a_{k_0+1}$，考虑他是否有策略保证自己先取 $a_{k_0+x_0+k_1+1}$。答案是肯定的，他只要根据 $k_1$ 的奇偶性决定是否取完 $a_{k_0+x_0}$

由此可见，$k_0$ 决定主动权归属，并且获得方可将主动权一直保持下去，直到自己一次性取完 $a_n$。所以可直接求前缀 $1$ 的个数

#include 
 
using namespace std;
 
const int N = 1e5 + 5;
int t, n, a[N];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i];

        int k = 0;
        while(k < n && a[k] == 1) k++;
        cout << ((k == n) ^ (k & 1) ? "Second" : "First") << "\n";
    }

    return 0;
}

SG 函数做法

定义 $SG(i, j)$ 为前 $i - 1$ 堆已取完，第 $i$ 堆还剩 $j$ 颗的状态。该状态的后继状态为前 $i - 1$ 堆已取完，第 $i$ 堆还剩 $k$ 颗，$k \in [0, j)$，则

$$ SG(i,j) = mex\{SG(i, 0), SG(i, 1), ..., SG(i, j-1)\} $$

由于是从后往前递推，初始状态为 $SG(n, j) = j$

考虑对状态转移做优化

$SG(i, 0) = SG(i+1, a_{i+1})$，因为它们都对应第 $i$ 堆已取完，第 $i+1$ 堆还未取，记 $x = SG(i, 0)$
1. 若 $x >= a_i$，已知 $SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i-1$ 项，根据 $mex$ 规则，$0,1,...,a_i-2$ 依次是它们的值，所以 $SG(i, a_i) = a_i - 1$
2. 若 $x < a_i$，$SG(i, 0), SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i$ 项，会不重不漏取完 $0,1,...,a_i-1$，所以 $SG(i, a_i) = a_i$

我们只需求 $SG(i, a_i)$，所以可以去掉第二维。由于是顺序取石子，能操作的有向图只有一张，所以必胜态是 $SG(1, a_1) \neq 0$

#include 
 
using namespace std;

const int N = 1e5 + 5;
int t, n, a[N], sg[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        sg[n] = a[n];
        for(int i = n - 1; i; i--)
            sg[i] = sg[i + 1] >= a[i] ? a[i] - 1 : a[i];
        
        cout << (sg[1] ? "First" : "Second") << "\n";
    }

    return 0;
}

The Proof of Correctness of Some of the Shortest Path Algorithms

LOGI — Sat, 05 Mar 2022 10:41:00 +0000

本文只对算法导论中文第 3 版中 Bellman-Ford，Dijkstra，Floyd-Warshall 算法的正确性证明进行非严谨重述。这些证明对堆优化版 Dijkstra 和队列优化版 Bellman-Ford，即 SPFA 同样适用，因为它们和原版没有本质不同

[...]

The Four Arithmetic Operation of BigInteger

LOGI — Tue, 04 Jan 2022 08:32:00 +0000

大整数的四则运算，很多数人都写过，本文提供一个 Java 版本的朴素实现，即模拟竖式。除法使用了递归，效率不高，递推公式如下：

求商 = 连接(
    被除数大于等于除数的最小前缀 / 除数,
    逐位连接(上式余数, 被除数剩余部分)[期间, 若连接后的被除数小于除数, 商上零],
    [连接完毕后, 若被除数不小于除数, 求商(连接后的被除数, 除数)]
)

当商高于一千位时，递归版本栈溢出，改为等价迭代后，一亿位被除数测试通过。

Java Implementation

package im.logi.math;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.function.BiFunction;
import java.util.stream.IntStream;

/**
 * @author logi
 * @version 1.0
 * @time 2022/1/5 16:08
 */
public class BigInteger implements Comparable, Cloneable {
    private static final BigInteger ZERO = new BigInteger("0");
    private static final BigInteger ONE = new BigInteger("1");

    private boolean positive = true;
    private StringBuilder value;

    private BigInteger() {
        value = new StringBuilder();
    }

    public BigInteger(String valueString) {
        int beginIndex = 0;
        if (valueString.charAt(0) == '-') {
            beginIndex = 1;
            positive = false;
        } else if (valueString.charAt(0) == '+') beginIndex = 1;
        while (beginIndex < valueString.length()
                && valueString.charAt(beginIndex) == '0') beginIndex++;

        // 仅是一个符号或全部为零，回退
        if (beginIndex == valueString.length()) beginIndex--;

        value = new StringBuilder(valueString.length() - beginIndex);
        for (int i = beginIndex; i < valueString.length(); i++) {
            char c = valueString.charAt(i);
            if (c < '0' || c > '9') throw new IllegalArgumentException();
            value.append(c);
        }

        setZeroPositive();
    }

    // 只存正零
    private void setZeroPositive() {
        if (value.length() == 1 && value.charAt(0) == '0')
            positive = true;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        BigInteger clone = (BigInteger) super.clone();
        clone.positive = positive;
        clone.value = new StringBuilder(value);
        return clone;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof BigInteger o)
            return positive == o.positive
                    && value.toString().equals(o.value.toString());

        return false;
    }

    @Override
    public int compareTo(BigInteger o) {
        if (positive != o.positive) return positive ? 1 : -1;

        int absRet = value.length() - o.value.length();
        if (absRet != 0) return positive ? absRet : -absRet;

        for (int i = 0; i < value.length(); i++) {
            absRet = get(i) - o.get(i);
            if (absRet != 0) break;
        }

        return positive ? absRet : -absRet;
    }

    @Override
    public String toString() {
        return (positive ? "" : "-") + value;
    }

    // 相反数，拷贝返回
    public BigInteger negative() {
        BigInteger negative;
        try {
            negative = (BigInteger) clone();
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException();
        }
        negative.positive = !positive;
        negative.setZeroPositive();
        return negative;
    }

    // 绝对值，拷贝返回
    public BigInteger absolute() {
        BigInteger absolute = negative();
        absolute.positive = true;
        return absolute;
    }

    private int get(int index) {
        return value.charAt(index) - '0';
    }

    private void set(int index, int place) {
        value.setCharAt(index, (char) (place + '0'));
    }

    // 去除前导零，时间复杂度 O(n)
    private void trimZero() {
        int i = 0;
        // 唯一零不处理
        //noinspection StatementWithEmptyBody
        for (; i < value.length() - 1 && get(i) == 0; i++) ;
        value.delete(0, i);
    }

    // 加
    public BigInteger add(BigInteger second) {
        if (positive != second.positive) {
            return positive
                    ? subtract(second.negative())
                    : second.subtract(negative());
        }

        // 以下为同号情况
        BigInteger sum = new BigInteger();
        sum.positive = positive;

        BigInteger longer = this;
        BigInteger shorter = second;
        if (value.length() < second.value.length()) {
            longer = second;
            shorter = this;
        }

        // 多开一位
        for (int i = 0; i <= longer.value.length(); i++) sum.value.append(0);

        int i = longer.value.length() - 1;
        int j = shorter.value.length() - 1;
        for (; j >= 0; i--, j--) {
            int k = i + 1;
            int s = longer.get(i) + shorter.get(j) + sum.get(k);
            sum.set(k, s % 10);
            sum.set(i, s / 10);
        }
        for (; i >= 0; i--) {
            int k = i + 1;
            int s = longer.get(i) + sum.get(k);
            sum.set(k, s % 10);
            sum.set(i, s / 10);
        }

        sum.trimZero();
        return sum;
    }

    // 减
    public BigInteger subtract(BigInteger second) {
        if (equals(second)) return ZERO;

        if (positive != second.positive) {
            return positive
                    ? add(second.negative())
                    : second.add(negative()).negative();
        }

        BigInteger abs = absolute();
        BigInteger secAbs = second.absolute();
        if (abs.compareTo(secAbs) < 0) {
            BigInteger diff = secAbs.subtract(abs);
            diff.positive = !positive;
            return diff;
        } else if (!positive) {
            BigInteger diff = abs.subtract(secAbs);
            diff.positive = false;
            return diff;
        }

        // 以下为全正且 this > second 的情况
        BigInteger diff = new BigInteger();
        if (value.length() == 1) {
            diff.value.append(get(0) - second.get(0));
            return diff;
        }

        // 多开一位
        diff.value.append(0);
        diff.value.append((char) ('0' - 1));
        for (int i = 2; i < value.length(); i++) diff.value.append(9);
        diff.value.append((char) ('9' + 1));

        int i = value.length() - 1;
        int j = second.value.length() - 1;
        for (; j >= 0; i--, j--) {
            int k = i + 1;
            int d = get(i) - second.get(j) + diff.get(k);
            diff.set(k, d % 10);
            diff.set(i, d / 10 + diff.get(i));
        }
        for (; i >= 0; i--) {
            int k = i + 1;
            int d = get(i) + diff.get(k);
            diff.set(k, d % 10);
            diff.set(i, d / 10 + diff.get(i));
        }

        diff.trimZero();
        return diff;
    }

    // 乘
    public BigInteger multiply(BigInteger second) {
        if (equals(ZERO) || second.equals(ZERO)) return ZERO;

        BigInteger oneMul = null;
        if (absolute().equals(ONE)) oneMul = second;
        else if (second.absolute().equals(ONE)) oneMul = this;
        if (oneMul != null)
            return positive == second.positive
                    ? oneMul.absolute()
                    : oneMul.absolute().negative();


        BigInteger product = new BigInteger();
        product.positive = positive == second.positive;

        for (int i = 0; i < value.length() + second.value.length(); i++)
            product.value.append(0);

        for (int i = value.length() - 1; i >= 0; i--) {
            for (int j = second.value.length() - 1; j >= 0; j--) {
                int h = i + j;
                int l = h + 1;
                int p = get(i) * second.get(j) + product.get(l);

                product.set(l, p % 10);
                product.set(h, p / 10 + product.get(h));
            }
        }

        product.trimZero();
        return product;
    }

    // 除
    public BigInteger divide(BigInteger second) {
        if (second.equals(ZERO)) throw new ArithmeticException();
//        if (equals(ZERO)) return ZERO;
        if (absolute().compareTo(second.absolute()) < 0) return ZERO;
        if (second.absolute().equals(ONE))
            return positive == second.positive
                    ? absolute()
                    : absolute().negative();
        if (absolute().equals(second.absolute()))
            return positive == second.positive
                    ? ONE
                    : ONE.negative();
        if (positive != second.positive)
            return absolute().divide(second.absolute()).negative();
        if (!positive)
            return absolute().divide(second.absolute());

        // 以下为全正且 this > second 的情况
        BigInteger quotient = new BigInteger();
        quotient.positive = true;

        BigInteger dividend = this;
        outer:
        while (true) {
            BigInteger diff = new BigInteger();
            int i = 0;
            // this > second，总能取到 diff > second，不会越界
            do {
                diff.value.append(dividend.get(i++));
            } while (diff.compareTo(second) < 0);

            // diff >= second 首次成立, 商至少为 1 且不大于 9
            int c = 1;
            //noinspection StatementWithEmptyBody
            for (; (diff = diff.subtract(second)).compareTo(second) >= 0; c++) ;
            quotient.value.append(c);

            if (i >= dividend.value.length()) break;

            BigInteger rest = new BigInteger();
            if (diff.equals(ZERO)) {
                // 除尽，检查后续若干零
                while (dividend.get(i++) == 0) {
                    quotient.value.append(0);
                    if (i >= dividend.value.length()) {
                        break outer;
                    }
                }
            } else {
                // 未除尽，余数作下一轮被除数前缀
                rest.value.append(diff.value);
            }

            // 若必要，商补若干零
            do {
                rest.value.append(dividend.get(i++));
                if (rest.compareTo(second) < 0) quotient.value.append(0);
                else break;
                if (i >= dividend.value.length()) break outer;
            } while (true);

            rest.value.append(dividend.value.substring(i));

            if (rest.compareTo(second) < 0) break;

            dividend = rest;
        }

        return quotient;
    }

    public static void testOperation(
            BiFunction testedOperation,
            BiFunction standardOperation,
            char operator,
            String a,
            String b
    ) {
        Exception testedException = null;
        BigInteger testedResult = null;
        try {
            testedResult = testedOperation.apply(new BigInteger(a),
                    new BigInteger(b));
        } catch (Exception e) {
            testedException = e;
        }

        Exception expectedException = null;
        java.math.BigInteger expectedResult = null;
        try {
            expectedResult = standardOperation.apply(new java.math.BigInteger(a),
                    new java.math.BigInteger(b));
        } catch (Exception e) {
            expectedException = e;
        }

        if (expectedException != null && testedException != null) return;

        if (expectedException != null) {
            System.out.printf("The result is wrong: %s %s %s = %s, got %s\n",
                    a, operator, b, expectedException, testedResult);
            throw new RuntimeException();
        }

        if (testedException != null) {
            System.out.printf("The result is wrong: %s %s %s = %s, got %s\n",
                    a, operator, b, expectedResult, testedException);
            throw new RuntimeException();
        }

        if (!testedResult.toString().equals(expectedResult.toString())) {
            System.out.printf("The result is wrong: %s %s %s = %s, got %s\n",
                    a, operator, b, expectedResult, testedResult);
            throw new RuntimeException();
        }
    }

    public static void testOne(List pair) {
        testOperation(BigInteger::add, java.math.BigInteger::add,
                '+', pair.get(0), pair.get(1));
        testOperation(BigInteger::subtract, java.math.BigInteger::subtract,
                '-', pair.get(0), pair.get(1));
        testOperation(BigInteger::multiply, java.math.BigInteger::multiply,
                'x', pair.get(0), pair.get(1));
        testOperation(BigInteger::divide, java.math.BigInteger::divide,
                '/', pair.get(0), pair.get(1));
    }

    public static void testAll(List pair) {
        List> cases = List.of(
                List.of(pair.get(0), pair.get(1)),
                List.of(pair.get(0), "-" + pair.get(1)),
                List.of("-" + pair.get(0), pair.get(1)),
                List.of("-" + pair.get(0), "-" + pair.get(1))
        );
        cases.forEach(BigInteger::testOne);

        if (pair.get(0).equals(pair.get(1))) return;

        cases.stream().map(p -> List.of(p.get(1), p.get(0)))
                .forEach(BigInteger::testOne);
    }

    public static String generateRandomBigInteger(int spaceBound) {
        spaceBound = Math.max(spaceBound, 1001);
        Random r = new Random();
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < r.nextInt(spaceBound - 1000, spaceBound); i++) {
            s.append(r.nextInt(0, 10));
        }
        return s.toString();
    }

    public static void main(String[] args) {
        // If no exception thrown during execution, test will pass.
        int spaceBound = 100000;
        List> cases = new ArrayList<>(List.of(
                List.of("0", "0"),
                List.of("0", "34291743"),
                List.of("1", "1"),
                List.of("1", "3247091"),
                List.of("7", "392"),
                List.of("000007", "392"),
                List.of("7", "00000392"),
                List.of("0007", "00000392"),
                List.of("0007", "sa23bcd"),
                List.of("---3427190", "sa23bcd"),
                List.of("++34721", "32147"),
                List.of("432134", "842097")
        ));
        IntStream.range(0, 10).forEach(_ignored -> cases.add(
                List.of(generateRandomBigInteger(spaceBound),
                        generateRandomBigInteger(spaceBound))));
        cases.forEach(BigInteger::testAll);
    }
}

Rust Implementation

本文链接生成方法

"The Four Arithmetic Operation of BigInteger".split(" ").map(word => word.toLowerCase()).join("-")

IEEE 754 基本浮点数的精度和范围

EnumSet

LOGI — Wed, 07 Jul 2021 16:00:00 +0000

枚举大量用于条件判断，如果要判断对象同时满足多个条件，或者满足其中之一，可将多个枚举实例存入 Set，使用集合操作 contains 或 containsAll 完成判断，我们希望这些操作都能以少于 O(n) 的时间完成。Java 中的 EnumSet 是一个使用 位数组 辅助实现的专门操作枚举类型元素的高性能集合。它是一个抽象类，有两个实现类，分别为 RegularEnumSet 和 JumboEnumSet。前者用来处理常量数小于等于 64 的枚举，后者处理超过 64 个常量的情况。我们着重分析两个实现类的 add, remove, contains 和 containsAll 方法，观察位数组如何使枚举集合变得高效。

[...]

SkipList

LOGI — Fri, 02 Jul 2021 16:45:00 +0000

SkipList 译为跳跃列表，常简称跳表，是一种用于快速查找的数据结构，由美国计算机科学家 William Pugh（威廉·普） 于 1990 年在论文 Skip lists: A probabilistic alternative to balanced trees 中提出。发明者认为，跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。由于时间复杂度与红黑树相当，且实现简单，两者常常被相互比较。它不像红黑树需要复杂的再平衡，有利于并发操作。

[...]

约瑟夫环

LOGI — Sat, 18 Apr 2020 18:55:00 +0000

据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

[...]

LOGI - 算法

Proof of Lucas' theorem

The Theorem

Inference

The Proof

Implementation of Variable Layer Loops and a Generalized Method for Recursive to Non-Recursive Conversion

Problem

Bindian Signalizing

Reverse a Stack Only with Recursion and That Stack

Sequential Nim

题目翻译

最优解

SG 函数做法

The Proof of Correctness of Some of the Shortest Path Algorithms

The Four Arithmetic Operation of BigInteger

Related

EnumSet

SkipList

约瑟夫环