标签:矩阵

【题解】 刷题比赛 (矩阵快速幂) (luoguP1707)

按照题目提示,构造矩阵,用矩阵快速幂求解

构造矩阵:

大家一定做过这种题:求斐波那契数列第N项%1e9+7(N<=1e18)
单纯从数学上讲,我们可以使用矩阵快速幂解决。由于斐波那契数列的递[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】浅谈k进制矩阵快速幂求解类斐波那契问题 ——litble

例题引入

CLG是一个喜欢打篮球的人,他身体强壮,球技高超,成为了学校篮球队的队长。
为了锻炼腿部肌肉的力量,CLG每天都在做跳台阶的锻炼。他每次从地面(第0级台阶)开始,他会每一步往上跳若干级台阶[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Scout YYF I (POJ3744) 概率DP+矩阵快速幂

[latexpage]

题意:特工YYF潜入敌方根据地,历经千辛万苦后他站在了一条地雷路的第一格。伴随着音乐和鼓点,他每一步有p的概率往前走一格,(p-1)的概率跳过一格到达第二格。求他生还的概率。[......]

[继续阅读= ̄ω ̄=]

Read MoreComment