P1654 OSU! 题解
好题！但不得不说早期洛谷的题解质量是真的差，感觉没有一篇题解是讲的特别清楚的，我看了好久才搞懂。下面是我认为的一种更规范的解题过程。
首先，我们设随机变量 \(X_i\) 表示从 \(i\) 向左的极长 1 串的长度，并且对于任意的 \(i\)，我们要想办法求出 \(E(X_i^3)\)。（需要注意的是 \(E(X^3) \not = (E(X))^3\)。更一般地说，\(E(f(X)) \not = f(E(X))\)。）但直接求是不好求的，我们先考虑求出 \(E(X_i)\) 和 \(E(X_i^2)\)。
-
\(E(X)\)：如果第 \(i\) 位是 \(0\)，那么 \(X_i = 0\)；否则，“从 \(i\) 向左的极长 1 串的长度”就等于“从 \(i-1\) 向左的极长 1 串的长度”再加 \(1\)，即 \(X_i = X_{i-1} + 1\)（当然 \(X_{i-1}\) 可以是 \(0\)。）。根据期望的可加性，就有 \(E(X_i) = (1-p_i) \cdot 0 + p_i \cdot (E(X_{i-1}) + 1) = p_i \cdot (E(X_{i-1}) + 1)\)。
（这里第 \(i\) 位是 \(0\) 的情况并不对答案产生贡献，因为乘上了 \(0\)，并且在 \(E(X^2)\) 和 \(E(X^3)\) 的推导中也是如此，所以下面不再讨论这种情况。）
其实这里的转移是较为明显的，但它运用的期望的重要性质——可加性将会在下面的推导中也用到，因此需要格外注意。
-
\(E(X^2)\)：这里是重点。回忆一下，在上面的推导中，我们把 \(X_i\) 表示成了两部分：\(i\) 向左（不包含 \(i\)）的部分——\(X_{i-1}\) 和第 \(i\) 位本身——\(1\)。能否把 \(X_i^2\) 也分成两部分表达？
确实是可以的。因为已经假定了第 \(i\) 位是 \(1\)，所以 \(X_i = X_{i-1} + 1\)。进一步地，\(X_i^2 = ((X_i - 1) + 1)^2 = (X_{i-1} + 1)^2 = X_{i-1}^2 + 2X_{i-1} + 1\)。这样就成功地用下标小于 \(i\) 的式子表达出了 \(X_i^2\)！再次利用期望的可加性，就有 \(E(X_i^2) = p_i \cdot(E(X_{i-1}^2) + 2E(X_{i-1}) + 1)\)。
-
\(E(X^3)\)：既然已经推导出了 \(E(X^2)\)，那么这里也只需依葫芦画瓢了。
因为 \(X_i^3 = (X_{i-1} + 1)^3 = X_{i-1}^3 + 3X_{i-1}^2 + 3X_{i-1} + 1\)
根据期望的可加性，有 \(E(X_i^3) = p_i \cdot (E(X_{i-1}^3) + 3E(X_{i-1}^2) + 3E(X_{i-1}) + 1)\)。
到这里，本题的大部分推导都完成了，但仍没有结束。如果直接输出 \(E(X_n^3)\)，那么是不对的，因为 \(E(X_n^3)\) 只表示从第 \(n\) 位向左这个串得到的分数，而不代表总分。
设 \(Y_i\) 表示截至到第 \(i\) 位能得到的分数，那么
-
如果第 \(i\) 位为 \(0\)：显然 \(Y_i = Y_{i-1}\)。
-
如果第 \(i\) 位为 \(1\)：这里，我们希望把 \(Y_i\) 表示成 \(Y_{i-1} + \Delta\) 的形式，其中 \(\Delta\) 表示在第 \(i\) 位的“得分增量”，它应该是 \(X_i^3 - X_{i-1}^3\)——这一部分之前已经推导过了，即 \(E(\Delta) = E(X_i^3 - X_{i-1}^3) = 3E(X_{i-1}^2) + 3E(X_{i-1}) + 1\)。代回，就得到了最终的式子：
\[E(Y_i) = E(Y_{i-1}) + 3E(X_{i-1}^2) + 3E(X_{i-1}) + 1 \]输出答案为 \(E(Y_n)\)。\(\Box\)