LOGI
https://logi.im/
记录自己创造的 BUG!
-
Proof of Lucas' theorem
https://logi.im/algorithm/proof-of-lucas-theorem.html
2023-12-22T11:30:00+00:00
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
https://logi.im/algorithm/implementation-of-variable-layer-loops-and-a-generalized-method-for-recursive-to-non-recursive-conversion.html
2023-08-16T10:23:00+00:00
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);以上代码输出如下: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 语句,这种硬编码方式无法应对循环层数可变的情况。备用解决方案是动态生成源码文本,创建编译或解释器进程执行,但这肯定不是我们想要的。[...]
-
Common Encoding Implementation
https://logi.im/back-end/common-encoding-implementation.html
2023-05-26T17:19:00+00:00
本文将介绍几种常见信息编码标准,并用 JavaScript 对其实现,包括 UTF-8,Base58, Base64, URL Encode。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 编码的转换规则。First code pointLast code pointByte 1Byte 2Byte 3Byte 4U+0000U+007F0xxxxxxx U+0080U+07FF110xxxxx10xxxxxx U+0800U+FFFF1110xxxx10xxxxxx10xxxxxx U+10000U+10FFFF11110xxx10xxxxxx10xxxxxx10xxxxxx例如,汉字 “中” 的 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;
}BaseNBaseN 是一类 binary-to-text(二进制转文本)编码方法,其用 N 种字符表示二进制数据,包括 Base64, Base58 等。其实质是将编码后的字符串看成一个 N 进制整数,每个字符对应整数的一位。例如,十进制数 255 是 Base10 编码,其 Base2 编码即为其二进制 1111 1111,Base8 编码即为其八进制 377,Base16 编码即为其十六进制 FF,以此类推。Base58顾名思义,Base58 使用 58 种字符编码数据,其知名用途是比特币的钱包地址编码,中本聪在代码注释中给出了他的使用意图。避免混淆。在某些字体下,数字 0 和字母大写 O,以及字母大写 I 和字母小写 l 会非常相似。不使用 "+" 和 "/" 的原因是非字母或数字的字符串作为帐号较难被接受。没有标点符号,通常不会被从中间分行。大部分的软件支持双击选择整个字符串。以下是 Base58 码表。ValueCharacterValueCharacterValueCharacterValueCharacter0112233445566778899A10B11C12D13E14F15G16H17J18K19L20M21N22P23Q24R25S26T27U28V29W30X31Y32Z33a34b35c36d37e38f39g40h41i42j43k44m45n46o47p48q49r50s51t52u53v54w55x56y57z上文提到 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)2 = (16)10(010000)2 = (16)10(000000)2 = (0)10(000000)2 = (0)10通过查表,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 EncodingURL 编码用于将任意数据置于 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 仓库,文中的表述和代码可能存在错误,如有发现请在评论区留言,感谢阅读。Referenceshttps://en.wikipedia.org/wiki/Unicodehttps://en.wikipedia.org/wiki/UTF-8https://developer.mozilla.org/en-US/docs/Glossary/Base64#solution_2_%E2%80%93_rewriting_atob_and_btoa_using_typedarrays_and_utf-8https://sf-zhou.github.io/programming/chinese_encoding.htmlhttps://learnmeabitcoin.com/technical/base58https://mp.weixin.qq.com/s/RYv1taUGhngyBX6M_W7ZiQhttps://en.wikipedia.org/wiki/Base64https://en.wikipedia.org/wiki/Binary-to-text_encodinghttps://kevin.burke.dev/kevin/node-js-string-encoding/https://en.wikipedia.org/wiki/URL_encodinghttps://en.wikipedia.org/wiki/MIMEhttps://www.freecodecamp.org/news/javascript-url-encode-example-how-to-use-encodeuricomponent-and-encodeuri/https://www.baeldung.com/java-url-encoding-decoding
-
Bindian Signalizing
https://logi.im/algorithm/bindian-signalizing.html
2022-05-07T10:50:00+00:00
这是 2010 年 Codeforces Beta Round #5 中的 E 题,曾在 2017 年 京东笔试 中出现,转载本题解请注明出处[...]
-
Reverse a Stack Only with Recursion and That Stack
https://logi.im/algorithm/reverse-a-stack-only-with-recursion-and-that-stack.html
2022-05-01T11:50:00+00:00
只用递归和自身反转栈,这题机试没法考,面试考纯属刁难,当作回溯练习食用最佳。[...]
-
Sequential Nim
https://logi.im/algorithm/sequential-nim.html
2022-04-03T09:48:00+00:00
题目翻译原题链接有 $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 <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$考虑对状态转移做优化$SG(i, 0) = SG(i+1, a_{i+1})$,因为它们都对应第 $i$ 堆已取完,第 $i+1$ 堆还未取,记 $x = SG(i, 0)$若 $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$若 $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;
}
-
The Proof of Correctness of Some of the Shortest Path Algorithms
https://logi.im/algorithm/the-proof-of-correctness-of-some-of-the-shortest-path-algorithms.html
2022-03-05T10:41:00+00:00
本文只对算法导论中文第 3 版中 Bellman-Ford,Dijkstra,Floyd-Warshall 算法的正确性证明进行非严谨重述。这些证明对堆优化版 Dijkstra 和队列优化版 Bellman-Ford,即 SPFA 同样适用,因为它们和原版没有本质不同[...]
-
Pure Shell Impl of Wechat and Telegram Push Service
https://logi.im/script/pure-shell-impl-of-wechat-and-telegram-push-service.html
2022-02-05T12:47:36+00:00
重写并开源了 Shell 版微信和电报消息推送,初衷是接收路由器 DDNS 通知。旧版依赖第三方接口,此次使用微信和 TG 官方 API 重构,代码也更加规范,你可以把它用在任何 *nix 设备,甚至是生产环境。[...]
-
A POSIX Compatible JSON Parser Written in AWK and Shell
https://logi.im/script/a-posix-compatible-json-parser-written-in-awk-and-shell.html
2022-02-04T19:47:00+00:00
Intro用 AWK 和 Shell 写了个简单的 JSON 解析器,初衷是方便我在路由器上编写 Shell 脚本。总大小 8K,POSIX 兼容,几乎可以运行于所有 *nix 系统。但因为性能不高,也没有做严格测试,如果不是设备空间不足不要使用。它的功能远没有知名项目 jq 强大,只能做字段提取,语法类似 JavaScript 访问对象属性。$ DOH_API='https://dns.alidns.com/resolve?name=dns.google&type=AAAA'
$ JQ_URI='https://ghproxy.com/https://raw.githubusercontent.com/vch'\
'eckzen/posix-awk-shell-jq/main/jq.sh'
$ curl -s "$DOH_API" | sh -c "$(curl -sL "$JQ_URI")" @ - 'Answer[0].data'
"2001:4860:4860::8888"#Details以下是实现思路:首先通过下表规则确定值类型,k 为键名,类型区分nullk 后首个冒号后首个非空白字符是 n布尔k 后首个冒号后首个非空白字符是 t/f数字k 后首个冒号后首个非空白字符是 数字字符串k 后首个冒号后首个非空白字符是 "对象k 后首个冒号后首个非空白字符是 {数组k 后首个冒号后首个非空白字符是 [数组元素k 形如 [num]接着根据类型分别找到起始字符,null 和 布尔 已由上一步确定。类型开始结束备注数字k 后首个数字下个非数字nullable字符串k 后首个 "下个非转义 "nullable对象k 后首个 {下个非嵌套对象内且非转义 }nullable,可跨行数组k 后首个 [下个非嵌套数组内且非转义 ]nullable,可跨行数组元素idx=0,[ 后;idx!=0,idx 个非嵌套对象内及非字符 , 后,首个非空白字符下个非嵌套对象内及非转义 , 或 ]nullable,可跨行最后,如果这个项目对你有帮助,请到 Github 上为我点颗星。如果在使用过程中遇到问题,也欢迎在页面下方留言。
-
Building Latest Frp for OpenWrt
https://logi.im/script/building-latest-frp-for-openwrt.html
2022-01-31T15:46:00+00:00
Compiling Machine$ uname -a
Linux codespaces_a8953f 5.4.0-1067-azure #70~18.04.1-Ubuntu SMP Thu Jan 13 19:46:01 UTC 2022 x86_64 x86_64 x86_64 GNU/LinuxTarget Machine# uname -a
Linux LOGI 3.14.79 #0 SMP Fri Feb 1 20:24:57 2019 mips PandoraBox
# cat /etc/openwrt_release
DISTRIB_ID="PandoraBox"
DISTRIB_CODENAME="19.02"
DISTRIB_RELEASE="19.02"
DISTRIB_VERSION="4802"
DISTRIB_REVISION="2019-02-01-git-93f2639a7"
DISTRIB_TARGET="ralink/mt7621"
DISTRIB_DESCRIPTION="PandoraBox 19.02 2019-02-01-git-93f2639a7"
DISTRIB_TAINTS="no-all busybox"
DISTRIB_MANUFACTURER="PandoraBox-Team"
DISTRIB_MANUFACTURER="http://www.pandorabox.com.cn"
# cat /proc/cpuinfo
system type : MediaTek MT7621
machine : Phicomm K2P
processor : 0
cpu model : MIPS 1004Kc V2.15
BogoMIPS : 583.68
wait instruction : yes
microsecond timers : yes
tlb_entries : 32
extra interrupt vector : yes
hardware watchpoint : yes, count: 4, address/irw mask: [0x0ffc, 0x0ffc, 0x0ffb, 0x0ffb]
isa : mips1 mips2 mips32r2
ASEs implemented : mips16 dsp mt
shadow register sets : 1
kscratch registers : 0
core : 0
VPE : 0
VCED exceptions : not available
VCEI exceptions : not available
# ...Install Build Tools$ sudo apt update
$ sudo apt install -y build-essential ccache flex gawk gettext git liblzma-dev libncurses5-dev libssl-dev python subversion u-boot-tools unzip wget xsltproc zlib1g-dev upx-uclDownload ToolChain$ TOOL_CHAIN_LOCATION=http://downloads.pangubox.com:6380/pandorabox/19.02/targets/ralink/mt7621/
$ TOOL_CHAIN_NAME=PandoraBox-SDK-ralink-mt7621_gcc-5.5.0_uClibc-1.0.x.Linux-x86_64-2019-02-01-git-0231ad4b5
$ curl -LO ${TOOL_CHAIN_LOCATION}${TOOL_CHAIN_NAME}.tar.xz
$ tar xf ${TOOL_CHAIN_NAME}.tar.xz
$ cd $TOOL_CHAIN_NAMEInstall Dependencies$ echo "src-git packages https://github.com/openwrt/packages.git" >> feeds.conf.default
$ ./scripts/feeds update -a
$ ./scripts/feeds install -aAdd Custom Packages$ git clone https://github.com/WingLim/pandorabox-k2p-package.git package/k2p
$ # Change the version number in package/k2p/frpc/Makefile.Select Packages$ make menuconfig
$ #Select [Network ---> Web Servers/Proxies ---> <*> frpc]Start Building$ make package/k2p/frpc/{clean,compile} V=sInstall Packages$ scp bin/packages/mipsel_1004kc_dsp/base/frpc_0.39.0-1_mipsel_1004kc_dsp.ipk home:/tmp
$ ssh home
# cd /tmp
# opkg install frpc_0.39.0-1_mipsel_1004kc_dsp.ipk
# rm -f frpc_0.39.0-1_mipsel_1004kc_dsp.ipkReferencesopenwrt/packagesopenwrt-frpHow to Build a Single PackageOpenWRT 自定义 ipk 编译减小 Go 代码编译后的二进制体积uci: Parse error (invalid command) at line 0, byte 0