推广 热搜: page  考试  小红  红书  数据  论文  数据分析  关键词  哪些  搜索 

hdu-4471-Homework-矩阵快速幂+优化加速

   日期:2024-12-17     移动:https://sicmodule.kub2b.com/mobile/quote/6434.html

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4471

题目意思:

求f(n).

当n为特殊点nk时

hdu-4471-Homework-矩阵快速幂+优化加速

解题思路:

当x不为特殊点时,直接用基本的矩阵快速幂,求出f[x],当x为特殊点时,用另外一个矩阵,左乘转移一下。

也就是按特殊点nk,将1-n分成很多区段,一个区段一个特殊点这样来回求。

两点优化:

1、因为要多次用到同一矩阵的快速幂,所以先预处理该矩阵的2K次幂,免的计算每个区间的时候,都要计算该矩阵的2K次幂。

2、矩阵相乘的时候,把K作为主要控制元,一次计算 a[i][k]*a[k][j] ,当有a[i][k]等于0时,直接跳出来。

注意:

矩阵大小的选取,位置的选放。

c1 c2 c3 ... ct    f(n-1)                  f(n)

 1  0   0   ... 0     f(n-2)                  f(n-1)

 0  1   0   ... 0     f(n-3)                  f(n-2)

 0  0   1   ... 0     ...                        ...

...   ....     ... .       ...                       ...

 0  0   0  ..1 0     f(n-t)                  f(n-t+1)

话不多说。

代码解释的很详细:

 



 

 

本文地址:https://sicmodule.kub2b.com/quote/6434.html     企库往 https://sicmodule.kub2b.com/ , 查看更多

特别提示:本信息由相关用户自行提供,真实性未证实,仅供参考。请谨慎采用,风险自负。


0相关评论
相关最新动态
推荐最新动态
点击排行
网站首页  |  关于我们  |  联系方式  |  使用协议  |  版权隐私  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报  |  鄂ICP备2020018471号