使用生成函数解掷骰子问题：概率与期望的数学魔法

"IOI2018中国国家候选队论文集" 这篇摘要主要涉及的是概率生成函数在解决算法竞赛中的掷骰子问题上的应用。概率生成函数是离散随机变量的一种数学工具，它能帮助我们处理非负整数集N上的随机变量的概率分布。在描述中，提到了概率生成函数的定义：对于数列a0, a1, a2, ..., 如果存在一个离散随机变量X使得Pr(X = i) = ai，那么这个数列的普通生成函数F(z) = E(zX)是一个无穷级数，其中E表示期望。 3.2.1部分讲述了概率生成函数的基本性质。首先，当z=1时，F(1)等于所有概率的和，即1，这是概率的归一性。其次，通过对F(z)求导，可以得到随机变量X的期望E(X) = F'(1)，而X的k次方的期望E(X^k) = F(k)(1)，这里的f(k)(x)表示f(x)的k阶导数。再者，通过进一步的导数运算，可以求得X的方差Var(X)。 文章接着提到了"border"的概念，对于一个长度为L的序列A，如果其前i个元素与后L-i+1个元素相同（即A[1, i] = A[L-i+1, L]），则A[1, i]是A的一个border。 4部分是基本题型示例，虽然没有具体题目内容，但可以理解为论文中会给出实际的算法竞赛题目，展示如何运用概率生成函数来解决问题。 整个摘要聚焦于概率生成函数在算法竞赛，特别是掷骰子问题中的应用。作者杨懋龙通过这种方式探讨了这类问题的解题策略，并强调了这种方法相对于传统方法的优势，如计算简便和扩展性强。论文还包括了其他主题，如后缀树、保序回归问题、树上连通块问题、平衡树、特殊数论函数求和问题、傅里叶变换在信息学竞赛中的应用，以及其他图论和组合数学相关问题的讨论。这些内容涵盖了广泛的理论和技术，适合对算法竞赛和数学应用感兴趣的人士阅读。