A – 小L的数列
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
自从NOIp 2018初赛第一次知道有数学期望这个东西起，我就一直很难理解。我一直没有去仔细的了解数学期望，而今天打了一场比赛，被逼着去了解了，现在我来写点东西记录一下这个概念。
\(数学期望\)是一个跟概率相关的概念。他的定义是：
数学期望是一个有限的事件的结果乘上一个事件的概率。
我们可以通过举例子来解释这个概念。比如取一个随机数（1-10之间），那么取到5的数学期望就是\(\frac {1} {2}\)。一般，我们用\(\mathbb{E}\)来表示这个值。
在本篇文章中，我只介绍一个性质。未来如果我学到了一些关于数学期望的新东西，那么我会把这些内容写在这篇文章里的。
数学期望在OI中比较重要的性质就是其线性性。简单来讲，如果有两个事件的数学期望为\(\mathbb{E}(a)\)和\(\mathbb{E}(b)\)，那么这两个事件叠加起来就是\(\mathbb{E}(a) + \mathbb{E}(b) = \mathbb{E}(a+b)\)。这个性质在OI中比较重要，一些题目会利用这个性质让解题者使用递推的方式解出答案。接下来我们看一道题目：
链接：T2062:随机数生成器
这道题目是我在华南师范大学附属中学举办的比赛中遇到的题目。虽然我这一题并没有AC，但是不妨碍我们来解释数学期望的一些性质和递推得解的方法。
我们来思考这样一个方程，设置\(\mathbb{E}(i)\)为输入为\(i\)的数学期望，那么，根据数学期望的线性性质，我们可以很容易推出以下方程：\[\mathbb{E}(i) =\frac {\mathbb{E}(1) + 1}{i} + \frac {\mathbb{E}(2) + 1}{i} + \frac {\mathbb{E}(3) + 1}{i} + \frac {\mathbb{E}(4) + 1}{i} + \dots + \frac {\mathbb{E}(i) + 1}{i}\]
而在本题中，可知\(\mathbb{E}(1) = 0\)。那么我们来变换一下式子，变成：\[\mathbb{E}(i) = \frac {\mathbb{E}(1) + \mathbb{E}(2) + \dots + \mathbb{E}(i – 1) + i}{n – 1}\]这样我们就可以递推出式子。
数学期望是OI中常见的概念，掌握它很有帮助。建议读者可以自己去阅读相关的资料，我在这里便不再描述。