111111111111111111

Question

循环矩阵的快速幂（bzoj 2510: 弱题）
有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

题目分析：

首先，我们需要知道什么是循环矩阵：由n个n维列向量（行向量也是可以的）首尾相连，组成了一个矩阵，称为n阶循环矩阵。

循环矩阵有下列性质：

（1）任何一行（列）的任意k个连续元素，就是循环矩阵通过首尾相连后的某一行（列）的连续k个元素。

（2）循环矩阵的秩为1。

题目所求是概率的期望，可以用期望的线性性质来求解，设f[i]表示有i种邮票时，需要的期望代价，那么对于i≥n，有

$$f[i]=\frac{1}{n}\times (f[i-1]+n)$$

$$f[i]=\frac{1}{n}\times (f[i-1]+n)=\frac{1}{n}\times f[i-1]+\frac{1}{n}\times n=f[i-1]+1$$

而i<n的情况比较特殊，我们可以建立状态矩阵：

$$\left|\begin{matrix}f[i]\f[i+1]\...\f[i+n-1]\end{matrix}\right|$$

此矩阵显然为一个n阶循环矩阵，为了方便起见，将其写成如下形式：

$$\left|\begin{matrix}x_1&x_2&...&x_{n-1}&x_n\ x_n&x_1&...&x_{n-2}&x_{n-1}\ ...&...&...&...&...\ x_2&x_3&...&x_n&x_1\end{matrix}\right|$$

可知这是一个n阶循环矩阵，因此可对其进行快速幂运算。

时间复杂度：O(n^3log k)

做法如下：

（1）初始化

$$\left|\begin{matrix}f[1]&f[2]...&f[n]\end{matrix}\right|\times \left|\begin{matrix}1&1&...&1&1\ n-1&n&...&3&2\ n-2&n-1&...&2&1\ ...&...&...&...&...\ 2&3&...&n&1\end{matrix}\right|\to \left|\begin{matrix}f[n+1]&f[n+2]&...&f[2n]\end{matrix}\right|$$

（2）矩阵相乘

$$\left|\begin{matrix}f[i]&f[i+1]&...&f[i+n-1]\end{matrix}\right|\times \left|\begin{matrix}1&1&...&1&1\ n-1&n&...&3&2\ n-2&n-1&...&2&1\ ...&...&...&...&...\ 2&3&...&n&1\end{matrix}\right|\to \left|\begin{matrix}f[i+n]&f[i+n+1]&...&f[i+2n-1]\end{matrix}\right|$$

（3）可以通过n次矩阵相乘，来得到所有状态f[1]到f[n]的值。

最终答案即为f[n]。

代码如下：