10.5

周日

两日摆烂生活

国庆在乡下生活，忘带褪黑素了，导致入睡完全成为了灾难。以前睡前读电子书的方法也不管用了，完全没有困意。昨天和今天中午又都出去吃饭，导致不能睡到十二点多。两个因素加起来，导致这两天和似了一样，几乎什么都没干——代码也没写，书也没看。

最后，今晚看了打 HelloHPC 期间漏掉的一节组合数学课和 notes，学到了很多。最有趣的是通过转变视角，利用容斥原理给出了 permanent of 0-1matrix 的一个复杂度比硬算更低的公式^[1]，这对应《生成函数论》里讨论的 Rooks on chessboards 问题，同样在容斥原理部分，但书中只是给出了一个不可计算的关系式，没有进一步探讨。薄纱！同时，课上关于 EGF 的指对关系利用符号化方法给出了直观的解释，比书中冗长的构建优雅也简单许多，再次薄纱！现在看来，读完此书不过是稍微扎实了一下基本功，加深记忆，然后多学了个拉格朗日反演罢了......

战 Gap Theorem

看完组合数学课，去刷水源，看到 “投喂可爱计算复杂性” ^[2]的楼主发了 Gap Theorem 的证明 slides，附上了自己写的证明概览和评注，然后希望有源 u 来评价一下自己写得对不对。乐于助人的我，立刻现场学习了一下 Gap Theorem 的证明，然后指出评注里有两个问题。lz 指出第二个问题是 slides 笔误了，把 $\omega$ 打成了 $o$ ，他直接抄下来没仔细看。但是第一个问题他没错。

我针对第一个问题进行了反驳，但他指出，我的反驳是错的，并且贴心地给出了时间复杂度类的定义，我这才想起来时间复杂度类的定义允许常数因子 $c$，所以他说的没错，我前面完全是云玩行为，非常小丑。但其中一个原因是，他实际上在关键的地方笔误了，而笔误后的评注确实是错误的，导致我不能理解他想干什么，所以才有了后续的跨服交流行为。

最后，我承认他的想法是完全正确的，只是有笔误。然后，他的构造里有一个放缩，我展示了一下如果不放缩，而是凹到 Linear Speedup Theorem 的下界，这个构造需要怎样的额外技术细节。

这样的友好交流^[3]真是令人心情愉悦啊，最终帮 lz 改了两个笔误，但是自己学到了很多！这就是水源！