对于非负整数 $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$ 都成立。

1. 已证 $i = 1$ 时，上式成立。

2. 假设当 $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$，等式仍然成立。

平常我们最多只写 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);

以上代码输出如下：

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

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

[...]

UTF-8

在 Unicode（统一码）系统中，每个字符对应一个码点（一个无符号整数）。一段文本中所有字符对应一段码点序列，通过某种转换，可将序列映射为若干字节，以便进行存储和网络间传输。UTF（the Unicode Transformation Format）统一码转换格式，即是一类映射方法，包括 UTF-8，UTF-16, UTF-32, UTF-EBCDIC。其中的 UTF-8 是一种变长 Unicode 编码方法，其将不同 Unicode 码点存储为 1 到 4 字节不等的单元，对于 ASCII 码点范围，使用 1 字节编码，以兼容 ASCII，变长有利于节省空间。下表给出了从 Unicode 码点到 UTF-8 编码的转换规则。

例如，汉字 “中” 的 Unicode 码点为 \u4e2d，位于上表第三行范围，因此需要 3 字节存储，将其二进制 0100 1110 0010 1101 各位从高到低依次取出，置于上表第三行的 xxxx 处，即完成编码。编码后的二进制为 1110 0100 1011 1000 1010 1101，十六进制为 \xe4\xb8\xad。

用代码实现也比较简单，翻译上表即可。

function unicodeArrToUtf8Arr(unicodeArr) {
  const buf = [];
  for (const code of unicodeArr) {
    let rest = 0;

    // encode the first byte
    if (code < 0x80) {
      // 0xxxxxxx
      buf.push(code);
    } else if (code < 0x800) {
      // 110xxxxx 10xxxxxx
      buf.push((0b110 << 5) | (code >> 6));
      rest = 1;
    } else if (code < 0x10000) {
      // 1110xxxx 10xxxxxx 10xxxxxx
      buf.push((0b1110 << 4) | (code >> 12));
      rest = 2;
    } else {
      // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
      buf.push((0b11110 << 3) | (code >> 18));
      rest = 3;
    }

    // encode the rest bytes
    while (rest-- > 0) {
      buf.push((0b10 << 6) | ((code >> (rest * 6)) & 0x3f));
    }
  }
  return buf;
}

以下是解码规则，是编码的逆操作。

function utf8ArrToUnicodeArr(utf8Arr) {
  const buf = [];
  for (let i = 0; i < utf8Arr.length;) {
    let _1 = utf8Arr[i++];
    let rest = 0;

    // decode the first byte
    if (_1 >> 7 === 0) {
      // 0xxxxxxx
      _1 &= 0b01111111;
    } else if (_1 >> 5 === 0b110) {
      // 110xxxxx 10xxxxxx
      rest = 1;
      _1 &= 0b00011111;
    } else if (_1 >> 4 === 0b1110) {
      // 1110xxxx 10xxxxxx 10xxxxxx
      rest = 2;
      _1 &= 0b00001111;
    } else {
      // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
      rest = 3;
      _1 &= 0b00000111;
    }

    // combine the rest bytes
    _1 <<= rest * 6;
    while (rest-- > 0) {
      _1 |= (utf8Arr[i++] & 0x3f) << (rest * 6);
    }
    buf.push(_1);
  }
  return buf;
}

BaseN

BaseN 是一类 binary-to-text（二进制转文本）编码方法，其用 N 种字符表示二进制数据，包括 Base64, Base58 等。其实质是将编码后的字符串看成一个 N 进制整数，每个字符对应整数的一位。例如，十进制数 255 是 Base10 编码，其 Base2 编码即为其二进制 1111 1111，Base8 编码即为其八进制 377，Base16 编码即为其十六进制 FF，以此类推。

Base58

顾名思义，Base58 使用 58 种字符编码数据，其知名用途是比特币的钱包地址编码，中本聪在代码注释中给出了他的使用意图。

1. 避免混淆。在某些字体下，数字 0 和字母大写 O，以及字母大写 I 和字母小写 l 会非常相似。
2. 不使用 "+" 和 "/" 的原因是非字母或数字的字符串作为帐号较难被接受。
3. 没有标点符号，通常不会被从中间分行。
4. 大部分的软件支持双击选择整个字符串。

以下是 Base58 码表。

上文提到 BaseN 编码的实质是将数据当成一个整数后转为 N 进制形式。扩展 ASCII 字符共 256 个，因此使用 ASCII 编码的字符串可看成一个 256 进制整数。例如，字符串 js 可当成一个 256 进制整数，其大小为 ascii(j) * 256 + ascii(s) = 106 * 256 + 115 = 27251 = 8 * 58^2 + 5 * 58^1 + 49，因此其 58 进制有 3 位，位值分别为 8，5，49，通过查 Base58 表，编码后的字符串为 96r 表示。

以上做法存在一个问题，如果 ASCII 编码字符串有若干 \0 前缀，由于 ascii(\0) = 0，如果把该字符串看成 256 进制整数，这些 \0 并不影响数值大小，例如，十进制 00012345 = 12345。即若完全按照进制转换方法编码，前导零值将丢失，虽然前导零不影响整数大小，但在原始二进制数据中一定有其存在意义，丢失是我们不愿看到的。为此，可在转换前数出前导零值个数，转换后补上相同个数的前导零值，这样就能将信息无损编码。

理解以上过程即可编写 Base58 编解码类。

class BxxConverter {
  static countLeadingElem(iter, obj) {
    let i = 0;
    for (; i < iter.length && iter[i] === obj; i++);
    return i;
  }

  static convert(fromBuf, fromBase, toBase) {
    const zeros = BxxConverter.countLeadingElem(fromBuf, 0);

    // convert a base xx buf to a base 10 big integer x
    let x = BigInt.fromBxxBuf(fromBuf.slice(zeros), fromBase);
    let r = 0;

    let buf = [];
    // calculate every position of x when converted to the object base number
    while (!x.isZero()) {
      // r = x % toBase, that's the current position
      [x, r] = x.div(toBase);
      buf.push(r);
    }

    if (zeros > 0) buf = buf.concat(new Array(zeros).fill(0));

    return buf.reverse();
  }
}

上述代码使用了大数类将原始数据转为十进制，再通过反复除 toBase 取余获得目标进制的每一位。实际上可以省去转十进制过程，直接做 fromBase 进制除法，相当于模拟高精度计算时的压位操作，读者可自行搜索。

Base64

理论上 Base64 也可使用以上通用方法转换，但对于以 2 的 n 次幂为基底的编码互转，有更简便的方法，可避免 BigInt 类的使用。这得益于以下观察：

二进制转八进制，只需将每 3 位看成一组，其十进制值即为一个八进制位。二进制转十六进制，只需将每 4 位看成一组，其十进制值即为一个十六进制位。依此类推，二进制转 64 进制，只需将每 6 位看成一组，其十进制值即为一个 64 进制位。

因此，要将任意二进制数据（以字节数组形式表示）转为 Base64，只需以每 6 位为一组，得到 64 进制下的码点，通过查表得到相应字符。反过来，要解码 Base64 字符串为二进制数据，只需将每个码点依次扩展为 6 位二进制，再以 8 位分组，得到相应字节。

需要注意的是，n 字节二进制数据共 8n 位，如果不能被 6 整除，以 6 位为一组，最后一组需要补充 6 - 8n % 6 位个 0。但在 Base64 标准中，为了填充的是整数字节（八位），且为了能在编码中直接看出填充的字节数，规定最后完全由填充形成的若干全零 6 位组，编码为 =，其个数等于填充的字节数。

记 r = 8n % 6，当其为 0 时无需填充，否则设需要填充 k 字节，则剩余的位数加上填充的位数等于 r + 8k = 6 + 6k，解得 k = 3 - r/2。由于 0 < r < 6，因此 0 < r / 2 < 3，只能取 1, 2。当 r/2 = 1 时，需要填充 2 字节，完全由填充形成的 6 位组也等于 2。当 r/2 = 2 时，需要填充 1 字节，完全由填充形成的 6 位组也等于 1。由于 8 和 6 的最小公倍数是 24，因此，可以把每 3 = 24 / 8 个字节当成一个最小批处理单元，编码为 4 = 24 / 6 个 Base64 码点。

举个例子，文本 A 的 ASCII 码为 65，二进制 0100 0001，占 1 字节。编码为 Base64 时，要填充 3 - 4 % 3 = 2 个全零字节，变为 0100 0001 0000 0000 0000 0000。以 6 位为一组编码为 Base64 刚好 4 个码点，分别是

• (010000)₂ = (16)₁₀
• (010000)₂ = (16)₁₀
• (000000)₂ = (0)₁₀
• (000000)₂ = (0)₁₀

通过查表，16 对应 Q，而最后两组完全是由填充形成的，因此最终编码为 QQ==。以下是 Base64 码表

                      Table 1: The Base 64 Alphabet

     Value Encoding  Value Encoding  Value Encoding  Value Encoding
         0 A            17 R            34 i            51 z
         1 B            18 S            35 j            52 0
         2 C            19 T            36 k            53 1
         3 D            20 U            37 l            54 2
         4 E            21 V            38 m            55 3
         5 F            22 W            39 n            56 4
         6 G            23 X            40 o            57 5
         7 H            24 Y            41 p            58 6
         8 I            25 Z            42 q            59 7
         9 J            26 a            43 r            60 8
        10 K            27 b            44 s            61 9
        11 L            28 c            45 t            62 +
        12 M            29 d            46 u            63 /
        13 N            30 e            47 v
        14 O            31 f            48 w         (pad) =
        15 P            32 g            49 x
        16 Q            33 h            50 y

以下是编解码实现。解码时，首先把后缀的若干 = 号去掉，因为它们完全是填充形成的，肯定不属于原始数据。此时 Base64 字符串最多只包含不足一字节的填充位，由于原始数据的字节数是整数，因此一定有 rawLen = floor(len(b64Str) * 6 / 8)，只要不断取 8 位单元，取完 rawLen 个字节即完成解码。

class Base64 {
  static b64CodeToAsciiCode(u6) {
    if (u6 < 26) {
      return u6 + 'A'.codePointAt(0);
    } else if (u6 < 52) {
      return u6 - 26 + 'a'.codePointAt(0);
    } else if (u6 < 62) {
      return u6 - 52 + '0'.codePointAt(0);
    } else if (u6 < 64) {
      return '+/'.codePointAt(u6 - 62);
    } else {
      throw new Error(`Invalid base64 code point: ${u6}.`);
    }
  }

  static asciiCharToB64Code(chr) {
    const diff = (c) => chr.codePointAt(0) - c.codePointAt(0);

    if (chr >= 'A' && chr <= 'Z') {
      return diff('A');
    } else if (chr >= 'a' && chr <= 'z') {
      return diff('a') + 26;
    } else if (chr >= '0' && chr <= '9') {
      return diff('0') + 52;
    } else if (chr === '+') {
      return 62;
    } else if (chr === '/') {
      return 63;
    } else {
      throw new Error(`Can't convert to base64 code from ASCII char: ${chr}.`);
    }
  }

  static encode(u8Arr) {
    let out = '';

    let mod = 2;
    for (let i = 0, u24 = 0; i < u8Arr.length; i++) {
      mod = i % 3;
      u24 |= u8Arr[i] << ((16 >> mod) & 24) /* 8 * (2 - mod) */ ;
      if (mod === 2 || i === u8Arr.length - 1) {
        out += String.fromCodePoint(
          Base64.b64CodeToAsciiCode((u24 >> 18) & 0x3f),
          Base64.b64CodeToAsciiCode((u24 >> 12) & 0x3f),
          Base64.b64CodeToAsciiCode((u24 >> 6) & 0x3f),
          Base64.b64CodeToAsciiCode(u24 & 0x3f)
        );
        u24 = 0;
      }
    }
    return out.substring(0, out.length - 2 + mod) + '='.repeat(2 - mod);
  }

  static decode(b64Str) {
    let pad = 0;
    for (let i = b64Str.length - 1; i > 0; i--) {
      if (b64Str[i] !== '=') break;
      pad++;
    }
    b64Str = b64Str.slice(0, b64Str.length - pad);

    const bLen = (b64Str.length * 3) >> 2; // Math.floor(len * 6 / 8)
    const buf = new Array(bLen);
    for (let i = 0, u24 = 0, bIdx = 0; i < b64Str.length; i++) {
      const mod = i & 3; // i % 4
      u24 |= Base64.asciiCharToB64Code(b64Str[i]) << (6 * (3 - mod));
      if ((mod === 3) | (i === b64Str.length - 1)) {
        for (let j = 0; j < 3 && bIdx < bLen; j++) {
          buf[bIdx++] = (u24 >> ((16 >> j) & 24)) & 0xff;
        }
        u24 = 0;
      }
    }

    return buf;
  }
}

URL Encoding

URL 编码用于将任意数据置于 URL 中，如果不编码，这些数据将与 URL 的保留字符冲突。一个 URL 格式可表示为

URI = scheme ":" ["//" authority] path ["?" query] ["#" fragment]
authority = [userinfo "@"] host [":" port]

可见 :/?#@ 等字符具有特殊含义，编码后的数据应不包含这些字符以避免歧义。如果数据中存在这些字符，应将其转为 ASCII 码的二位十六进制形式，并在前面加上百分号。对于非 ASCII 码数据，标准建议先使用 UTF-8 对其编码。URL 编码也用于发送 application/x-www-form-urlencoded 数据。以下是相应实现

const Utf8 = require('./utf8');

module.exports = class Url {
  static specialChr = '!*();:@&=+$,/?#[]% ';
  static hex = (b) => `%${b < 16 ? '0' : ''}${b.toString(16).toUpperCase()}`;

  static encode(raw) {
    let out = '';
    for (const c of raw) {
      const p = c.codePointAt(0);

      if (p >= 0x80 || Url.specialChr.includes(c)) {
        out += Utf8.unicodeArrToUtf8Arr([p]).map(Url.hex).join('');
        continue;
      }

      out += c;
    }

    return out;
  }

  static decode(encoded) {
    let out = '';

    for (let i = 0; i < encoded.length; ) {
      if (encoded[i] === '%') {
        const utfBuf = [];
        while (i < encoded.length && encoded[i] === '%') {
          utfBuf.push(parseInt(encoded.slice(i + 1, i + 3), 16));
          i += 3;
        }
        out += Utf8.unicodeArrToJsStr(Utf8.utf8ArrToUnicodeArr(utfBuf));
        continue;
      }

      out += encoded[i++];
    }

    return out;
  }
};

Conclusion

本文简要介绍了 UTF-8，Base58, Base64, URL Encode 编码的用途，方法，和关键代码实现。具体来说，用于将 Unicode 映射为字节序列的 UTF-8 编码，使全世界大多数国家的文字能以统一方法存储到计算机。BaseN 编码用于将二进制数据编码为文本，其实质是整数间的进制转换，当 N 为 2 的幂次方时，它们之间的转换可以通过位映射完成。URL 编码用于将数据安全地编码到网址中，或通过 HTTP 传送。

本文涉及的可运行代码见 Github 仓库，文中的表述和代码可能存在错误，如有发现请在评论区留言，感谢阅读。

References

• https://en.wikipedia.org/wiki/Unicode
• https://en.wikipedia.org/wiki/UTF-8
• https://developer.mozilla.org/en-US/docs/Glossary/Base64#solution_2_%E2%80%93_rewriting_atob_and_btoa_using_typedarrays_and_utf-8
• https://sf-zhou.github.io/programming/chinese_encoding.html
• https://learnmeabitcoin.com/technical/base58
• https://mp.weixin.qq.com/s/RYv1taUGhngyBX6M_W7ZiQ
• https://en.wikipedia.org/wiki/Base64
• https://en.wikipedia.org/wiki/Binary-to-text_encoding
• https://kevin.burke.dev/kevin/node-js-string-encoding/
• https://en.wikipedia.org/wiki/URL_encoding
• https://en.wikipedia.org/wiki/MIME
• https://www.freecodecamp.org/news/javascript-url-encode-example-how-to-use-encodeuricomponent-and-encodeuri/
• https://www.baeldung.com/java-url-encoding-decoding

[...]

[...]

原题链接

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

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

最优解

考虑几种特殊情形

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

考虑一般情形

$$ \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$

1. 由特殊情形 $2, 3$ 的分析可知，如果中间没有 $1$，$k_0$ 决定输赢
2. 如果中间有 $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 <bits/stdc++.h>
 
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$

考虑对状态转移做优化

1. $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 <bits/stdc++.h>
 
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;
}

[...]

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

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

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<BigInteger>, 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<BigInteger, BigInteger, BigInteger> testedOperation,
            BiFunction<java.math.BigInteger, java.math.BigInteger,
                    java.math.BigInteger> 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<String> 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<String> pair) {
        List<List<String>> 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<List<String>> 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);
    }
}

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

Related

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

[...]

[...]