AFAIK

注：这篇文章前半部分是八月底写的，后半部分想着别烂尾了所以十一月初才写的，看内容详尽程度明显可以看出来……（活动是七月底举办的，拖延程度可见一斑）

一年一度的 SIGYAO30 又要开办啦！今年的 SIGYAO30 定在西雅图，一来大家都还没去过西雅图，二来刚好有几个人在这里工作。

前几天和同事聊天，聊到前几天的北京数学高考题。最后一个题还挺有意思的，我和同事 yy 了好久都不会：

给定两个序列 \(\{a_i\}, \{b_i\} \in [n]^n\)，证明存在四个正整数 \(l_a \leq r_a, l_b \leq r_b\) 使得 \[\sum_{i=l_a}^{r_a} a_i = \sum_{i = l_b}^{r_b} b_i.\]

在想这个题的时候，我想到了曾经做 POI 的时候见过的一个题：

给定一个大小为 \(n\) 的序列 \(a\)，其中 \(a_i \in \{1, 2\}\)。

现在有 \(m\) 个询问，每次给定一个 \(k\)，要你找出一个和为 \(k\) 的子段，或者输出不存在。

数据范围为 \(n \leq 10^7, k \leq 10^5\)。

前几天在逛 论坛 的时候看到这么一句话：

Overloading in combination with Hindley-Milner is NP-complete.

后面的 Hinley-Milner 我不太懂，只知道是 Haskell 用的东西。但是前面这个 overloading 我还是知道是啥的。于是我就一时兴起，找到了这么一篇 文章，就证明在某种情况下，overloading 是 NP-complete 的。看起来这是 Programming Language （PL）领域的一个基础题：

In the 1986 version of the Dragon book, Exercise 6.25 is to show that overloading is NPcomplete: **6.25 The resolution of overloading becomes more difficult if identifier declarations are optional. More precisely, suppose that declarations can be used to overload identifiers representing function symbols, but that all occurrences of an undeclared identifier have the same type. Show that the problem of determining if an expression in this language has a valid type is NP-complete.

然而，作为一个完全没接触过 PL 的小白，我连里面的 notation 都看不懂，后来在 Understanding typing judgments 这篇文章的帮助下终于理解了之前的那篇文章在干些啥。这里就把它翻译成白话顺便魔改了一下证明，不需要 PL 预备知识也能看懂。

这是一个经典老题了，如何用 fair coins 来构造一个 biased coin，以及如何用 fair coins 来构造一个 discrete uniform distribution。基于这两个问题，我又 yy 了另外几个小 follow-up，试图去分析其时间复杂度。

中文版本请见这里。

\(\newcommand{\stirlingI}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}\) Lucas theorem is quite well known for compute \(\binom{n}{m} \pmod{p}\):

Let \(p\) be a prime, \(n = u_1 p + u_2\)，\(m = v_2 p + v_2\) where \(0 \leq u_2, v_2 < p\), then we have \[ \binom{n}{m} \equiv \binom{u_1}{v_1} \binom{u_2}{v_2} \pmod{p}. \]

However, Lucas theorem only works for prime \(p\). For composites CRT can rescue us, but we still have to solve the hard case where \(p\) is a prime power, which this post mainly discusses. The post borrows a lot from a post by prabowo (although I guess he also references min_25's blogpost), while having its own novelties (mostly the upper bound).

Andrew Granville also has a paper on Extended Lucas theroem. However, there are too many cases in the paper and the overall time complexity is also high. I'd never write it again after I did it once.

很久很久之前看到过这么一个问题：炉石里一套牌共有 30 张，问至少要探底多少次才能保证可以将牌库排序成想要的顺序？这里给不了解背景的朋友介绍一下，所谓 探底，就是选择牌库底三张牌中的一张将其至于牌库顶。

我们来抽象一下这个题：对于一个大小为 \(n\) 的排列 \(P\)，一次操作可以把前三个数中的一个塞到最后。既然这是个排序算法，我们不妨将其称作 探底排序 好了…… 那么现在问题就是问探底排序的最坏情况下需要多少次操作。我们先研究一个简化版，每次只能把前两个元素中的一个塞到最后。

作为一名 TCS 大师，我对这个问题挺有兴趣的。但是显然，求出精确解看起来非常难（而且我怀疑甚至不存在通项），于是就退而求其次，分析一下其时间复杂度好了。

近日听闻噩耗，Google CodeJam 要停止举办了：

After nearly 20 years of Code Jam, it's time to say goodbye. While Code Jam will not continue as planned, we invite you to participate in our Competitions' Farewell Round on Saturday, April 15 at 14:00 UTC.

去年以来整个硅谷都不景气，Google 也不例外开启了 大裁员模式 ，裁了 12k 人，即使在 2008 年经济危机的时候，Codejam 也坚持办了下去，但是现已加入 Killed by Google 荣誉套餐，真是可惜了……只能感慨，Google 再也不是当年的 Google 了……

近期看了《来自深渊》，《三体》（腾讯）和《三体》（艺画开天），评分如下：

• 《来自深渊》：6
• 《三体》（腾讯）：9
• 《三体》（艺画开天）：0

剧 透 警 告 ！

最近一时兴起更新了一下博客主题。三天打鱼两天晒网，文章没写多少，主题倒是一直在更新 2333……工欲善其事，必先利其器，再利其器，又利其器，复利其器，重利其器，更利其器，终忘其事……

几张拼图一展。