循环矩阵的快速幂(bzoj 2510: 弱题)
有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票,皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
111111111111111111
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- Kwan的解忧杂货铺@新空间代码工作室 2024-04-25 22:19关注
晚上好🌙🌙🌙
本答案参考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]。
代码如下:
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥20 python忆阻器数字识别
- ¥15 无法输出helloworld
- ¥15 高通uboot 打印ubi init err 22
- ¥20 PDF元数据中的XMP媒体管理属性
- ¥15 R语言中lasso回归报错
- ¥15 网站突然不能访问了,上午还好好的
- ¥15 有没有dl可以帮弄”我去图书馆”秒选道具和积分
- ¥15 semrush,SEO,内嵌网站,api
- ¥15 Stata:为什么reghdfe后的因变量没有被发现识别啊
- ¥15 振荡电路,ADS仿真