鏈接：https://ac.nowcoder.com/acm/problem/18987
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

qn是個(gè)特別可愛的小哥哥，qy是個(gè)特別好的小姐姐，他們兩個(gè)是一對好朋友 [ cp (劃掉~)
又是一年嚶花爛漫時(shí)，小qn于是就邀請了qy去嚶花盛開的地方去玩。當(dāng)qy和qn來到了田野里時(shí)，qy驚奇的發(fā)現(xiàn)，嚶花花瓣以肉眼可見的速度從樹上長了出來。
仔細(xì)看看的話，花瓣實(shí)際上是以一定規(guī)律長出來的，而且，每次張成新的花瓣的時(shí)候，上一次的花瓣就會都落到地上，而且不會消失。
花瓣生長的規(guī)律是，當(dāng)次數(shù)大于等于2時(shí)，第i次長出來的花瓣個(gè)數(shù)和上一次張出來的花瓣個(gè)數(shù)的差是斐波那契數(shù)列的第i-1項(xiàng)。初始的時(shí)候地上沒有花瓣，樹上的花瓣個(gè)數(shù)為1，第一次生長的花瓣個(gè)數(shù)為1。初始的那個(gè)花瓣就落到了地上
現(xiàn)在，小qn想知道，經(jīng)過k次生長之后，樹上和地上的總花瓣個(gè)數(shù)是多少?
ps:斐波那契數(shù)列:
f[1]=f[2]=1;f[i]=f[i-1]+f[i-2] (i>=2且i ∈ N+)

輸入描述:

一行一個(gè)數(shù)k

輸出描述:

一行一個(gè)數(shù)m，表示第k次生長過后，樹上和地上的總花瓣數(shù)是多少。由于答案會很大，請你將答案mod 998244353后輸出

題意不難理解，最終結(jié)果是要求斐波那契數(shù)列的前k+1項(xiàng)之和 ， 又因?yàn)镾n = f(n+2) - 1， 所以最后就是求 f(n+3)-1

普通的斐波那契數(shù)列求解可以用遞歸（時(shí)間復(fù)雜度O(2^N)），但是這里的數(shù)據(jù)太大，會超時(shí)，
所以這里用矩陣快速冪（時(shí)間復(fù)雜度O（logN））來求解。

[F(n),F(n-1)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-1)

F(n)的獲取方法有兩種

• 第一種，是取矩陣運(yùn)算結(jié)果的第一行第一列，
  由[F(n),F(n-1)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-1)得，矩陣運(yùn)算n-1次
• 第二種，取矩陣運(yùn)算結(jié)果第一行元素之和，
  由[F(n-1),F(n-2)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-2), F(n) = F(n-1)+F(n-2),矩陣運(yùn)算n-2次

GLOBAL_MOD = 998244353 k = int(input())""" 題意不難理解，最終結(jié)果是要求斐波那契數(shù)列的前k+1項(xiàng)之和 ， 又因?yàn)镾n = f(n+2) - 1， 所以最后就是求 f(n+3)-1普通的斐波那契數(shù)列求解可以用遞歸（時(shí)間復(fù)雜度O(2^N)），但是這里的數(shù)據(jù)太大，會超時(shí)， 所以這里用矩陣快速冪（時(shí)間復(fù)雜度O（logN））來求解。[F(n),F(n-1)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-1)F(n)的獲取方法有兩種 第一種，是取矩陣運(yùn)算結(jié)果的第一行第一列， 由[F(n),F(n-1)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-1)得，矩陣運(yùn)算n-1次 第二種，取矩陣運(yùn)算結(jié)果第一行元素之和， 由[F(n-1),F(n-2)] = [F(1), F(0)] * [[1 1] [1 0]]^(n-2), F(n) = F(n-1)+F(n-2),矩陣運(yùn)算n-2次 """ class Solution:def fib(self, n: int) -> int:if n < 2:return nres = self.matrixpower(n-1)res = res[0][0]-1res = res % GLOBAL_MODreturn resdef matrixpower(self, power):# res初始值為單位矩陣res = [[1, 0],[0, 1]] base = [[1, 1],[1, 0]] # 這個(gè)是我們根據(jù)斐波那契數(shù)列的特點(diǎn)構(gòu)造的矩陣 while power !=0:if power&1 !=0:res = self.multimatrix(res, base)power = power>>1base = self.multimatrix(base, base)return resdef multimatrix(self, m1, m2):n = len(m1)res = [[0]*n for i in range(n)]for i in range(n):for j in range(n):for k in range(n):res[i][j] = (res[i][j]+m1[i][k] * m2[k][j])%GLOBAL_MODreturn resans = Solution() print((ans.fib(k+3)))

總結(jié)

以上是生活随笔為你收集整理的牛客18987 粉嘤花之恋（矩阵快速幂、斐波那契数列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。