当一件事情有多种可能情况时，这件事情对某人而言具体是哪种情况的不确定性叫作熵。而能够消除该人对这件事情不确定性的事物叫作信息。熵和信息数量相等，意义相反，获取信息意味着消除熵。
熵和信息都是可以度量的。
当一件事情是每种情况的概率分布是 pip_i 时，它的熵就是

∑pilog⁡1pi(bit)\sum p_i\log\frac{1}{p_i}(bit)

其中 log⁡\log 一般以 22 为底。这其中的道理是把抛一枚硬币的不确定性看作单位 11，而因为不确定性的组合具有指数关系，所以要取一个 log⁡\log。

我们经常会遇到对一件大的不确定事件询问局部信息的情况，这时它提供的信息量就是当前这个局部的熵。

用例子来理解：基于比较的排序算法为什么下界 O(nlog⁡n)O(n\log n)？可以用鸽巢原理，但我们用信息熵来分析一下。这整个排列的熵是 log⁡(n!)=O(nlog⁡n)\log(n!)=O(n\log n)，而一次比较相当于是抛一次硬币，最多提供 11 的信息（我们在分析下界时都是假设我们对当前询问的局部一无所知，即每种情况的概率都相等，此时熵最大，得到信息最多）。于是我们就得到了下界。
而基数排序为什么可以更快？基数排序的基本操作是将一个数放到它对应的桶里。假设桶有 BB 个，则最多提供 log⁡B\log B 的信息。那么次数就可以分析为 O(nlog⁡nlogB)O(\frac{n\log n}{log B})？那么 BB 取 nn 即可得到 O(n)O(n)，明显错误。根据经验我们知道它还与值域有关，分析一下发现我们最后不仅得到了位置关系，还得到了每个数的值。那么假设值域为 ww，最初的熵就是 log⁡wn=nlog⁡w\log w^n=n\log w，次数为 O(nlog⁡wlog⁡B)O(n\frac{\log w}{\log B})。于是当值域小时可以做到 O(n)O(n)。

有趣的是，当我们对各种排序算法的每步提供的信息进行更细化的分析时，可以得到它们本质上为什么优和为什么劣。
还有一个比较有意思的结论是如果对一个符号系统（文字系统）求熵，那么它就等于这个符号系统的哈夫曼编码的平均长度。（这大概也是用bit这个单位的其中一个原因）

例题

交互题。
有一张试卷上有 nn 道判断题，答案只有对与错。我们每次可以填写所有题的答案（不允许不填），交上去之后系统会反馈答对多少道题。要求在 kk 次交卷之内获得满分。
n=1000,k=300n=1000,k=300 或 n=5000,k=1050n=5000,k=1050

这是 zzq在冬令营讲的，特别神仙的题。
考虑第一次询问都填对，这样可以得到对的题目的个数，设为 sumsum。然后接下来每次询问时把一个大小为 AA 的集合填成对，其他填成错。这时我们可以通过解方程得到 AA 中对的个数。具体地，若返回 xx，则个数为 x+A+sum−n2\frac{x+A+sum-n}{2}

注意到这个除 22 ，因为个数必须是整数，所以 x+A+sum−nx+A+sum-n 一定是偶数。这或许能提供更多的信息，若我们能得到这样的式子：x=y+z2x=\frac{y+z}{2}，其中 yy 是已经通过询问已知的，xx 是需要解方程求出的，zz 是一个未知的零一变量，那么我们就可以通过奇偶性得到 xx 和 zz。

注意到我们现在把询问转化为对一个集合的询问，所以可以考虑递归划分子问题。
设 F(S)F(S) 为一个子集的列表，执行这些询问之后可以得到子集 SS 的完整正确答案。
考虑将 SS 划分为两个大小相等的子集 S1,S2S_1,S_2，那么可以递归处理。然而如果直接做的话与暴力 O(n)O(n) 没有任何区别/cy。我们考虑上面的思路，需要构造 x=y+z2x=\frac{y+z}{2}。这个看起来就是解方程得到的，所以我们考虑来构造一个方程。在 F(S1),F(S2)F(S_1),F(S_2) 中分别拿出集合 A,BA,B。然后询问 A+B,S1−A+BA+B,S_1-A+B。我们如果事先知道 S1S_1 中的对的个数那么就可以解出 A,BA,B 了。注意要构造 2x+z2x+z，那么我们在其中一个询问集合中加入一个元素，即询问 A+B+{λ},S1−A+BA+B+\{\lambda\},S_1-A+B。
这时我们就构造出了那样的形式，即我们可以得到一个元素作为“赠品”。

来分析一下复杂度，用 (n,m)(n,m) 表示（元素个数，询问次数），那么我们可以有 (n,m)−>(2n+m−1,2m)(n,m)->(2n+m-1,2m)。即 mm 是得到正确答案的同时还要问一次整个 nn 个元素时的次数，那么转移时可以问一次 2n2n 个元素，问一次 nn 个元素，另外 nn 个元素的个数就已知了。剩下的 2m−22m-2 个询问每两个都有一个赠品。

设 n=kmn=km，则 (km,m)−>((2k+1)m−1,2m),k′=k+12(km,m)->((2k+1)m-1,2m),k'=k+\frac{1}{2}。即 kk 是随着迭代线性增长，而 mm 是指数增长，所以 n=O(mlog⁡m)n=O(m\log m)，m=(nlog⁡n)m=(\frac{n}{\log n})，求反函数主要是注意到 log⁡n\log n 和 log⁡m\log m 是同阶的。
我们得到了一个询问次数为 O(nlog⁡n)O(\frac{n}{\log n}) 的算法，打表一下发现可以通过。

现在用信息熵来分析一下，对于这张试卷，它的熵相当于 nn 个硬币，是 nn，而一次询问可以得到的信息最多为 log⁡n\log n，因为最多区分了 nn 种等概率事件。那么复杂度下界就是 O(nlog⁡n)O(\frac{n}{\log n})。这表明这个算法的阶达到了下界，是一个非常优秀的算法。

一道趣题

这题我想到了5胜3的其中一种做法，但是我并不会扩展QAQ，去翻了翻这个人下面的评论，有人给出了5胜3另一种解法，还扩展到了 3n+23n+2 胜 2n+12n+1，即解决了第一问。

先说我的做法。考虑我们显然可以至少胜 n/2n/2 次，即甲在第 2k−12k-1 次提示乙第 2k2k 次上帝出什么。怎么改进呢？注意到如果有连续相同颜色，那么可能只需要一次提示就可以得到超过 11 分。基于这个思路：
甲观察上帝的序列，如果第 22 和 33 相同，那么在第一次提示乙 22 的颜色， 22 和 33 得分，44 提示 55 的颜色，55 得分。
否则，如果 44 和 55 相同，那么分别在 2,4,52,4,5 得分，不再赘述。
否则，即 2,32,3 和 4,54,5 分别不同色，那么甲在 1,21,2 分别提示乙 4,54,5 的颜色。注意到这时甲1,21,2 出的颜色不同，而乙 22 与甲 11 出的相同，于是 22 不可能得分。这时乙就可以分辨出这是第三种情况，从而推断出 2,32,3 颜色不同，得知 33 的颜色，可以在 3,4,53,4,5 得分。

评论中的做法就更加简洁：
甲第一次提示乙 2,3,42,3,4 中颜色较多的那个，乙在 2,3,42,3,4 都出这个颜色，可以得到至少 22 分。而甲在 2,3,42,3,4 中颜色不同的那个位置提示乙 55 的颜色，可以在 55 得分。这个做法可以容易扩展：将 3n+23n+2 个位置掐头去尾之后 33 个一组，首尾各成一组，第 ii 组提示第 i+1i+1 组，即可得到 2n+12n+1 分。

考虑用信息熵去分析：我们如果用这样的模型：一个位置如果没有得分，那么可以提供 1bit1bit 的信息（因为上帝给出的颜色是初始随机的，所以没有意义），如果得分，那么乙已知这个位置，所以没有提供信息。

我们会疑惑地发现这样分析，这个问题是无解的！信息不够！而上面已经有了两个解决问题的实例，它们是如何工作的呢？

对于做法二，它的想法比较简单：1bit1bit 的信息不一定只能支持得到一分。它提高了信息的利用率。

对于做法一，它的想法就比较牛逼了：注意当上帝是第三种情况时，我们真的通过前两次得到了 3bit3bit 的信息！（第 44 位、第 55 位、2,32,3 不同）这是怎么做到的？注意在如此制定策略的情况下，一种进入情况三的情况出现的的概率是 18\frac{1}{8}。这时套用上面的公式得到它的信息量确实是 3bit3bit。而相应地，其他情况下得到的信息就会更少。

这就比较神奇了，我们通过对问题进行分析，设计一个更合理的策略，在需要更多信息的情形提供更多信息，在其他情形减少冗余的信息！这里的策略可能可以用语言来类比，因为在分析某种语言的熵时，并不是用它图像上的像素点或什么东西分析，而是套用上面的公式：一个字出现的概率越高，提供的信息就越少。（当然，我在想出这个做法时并没知道这背后有这么深刻的原理/cy，又经过一番思考之后才得到的）

对于解决 4n+14n+1 胜 3n3n 的终极问题，我觉得应该是需要综合这两种想法的。不过实在太过困难，等up更题解了。。

up主更了，很牛逼！其实这两种想法都是同一种想法，即对信息量公式的运用。对于做法二，它是给一些位置赋予了概率。比如给一个 11，是说接下来三个位置有两个 11，即每个位置有 0.660.66 的概率是 11。这样是利用了信息的公式，仍然是可以解释的。