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

時(shí)間限制：C/C++ 2秒，其他語(yǔ)言4秒
空間限制：C/C++ 131072K，其他語(yǔ)言262144K
64bit IO Format: %lld

題目描述

JYM和XJ轉(zhuǎn)眼就從小學(xué)上了高中。在學(xué)習(xí)遞推的時(shí)候，JYM在紙上隨手寫(xiě)了一個(gè)遞推關(guān)系式：an=2an-1，a0=0。寫(xiě)完這個(gè)遞推式，JYM拿給XJ看，XJ覺(jué)得太過(guò)簡(jiǎn)單，于是大筆一揮，在等式右邊又加了一個(gè)式子，變成了這樣：an=2an-1+n2。JYM看到這個(gè)式子，想要算幾個(gè)項(xiàng)來(lái)看看，可是一算就發(fā)現(xiàn)這個(gè)數(shù)據(jù)量太大了，你能幫他解決這個(gè)問(wèn)題嗎？

輸入描述:

輸入數(shù)據(jù)有多組（不超過(guò)100組數(shù)據(jù)），每組數(shù)據(jù)包含一個(gè)整數(shù)N<=10^18

輸出描述:

一個(gè)整數(shù)X，表示遞推式第n項(xiàng)的值。由于數(shù)字太大，因此結(jié)果對(duì)于1000000009取模后輸出。

構(gòu)造出來(lái)的基矩陣base:

GLOBAL_MOD = 1000000009 class Solution:def f(self, n: int) -> int:if n < 2:return nres = self.matrixpower(n-1)res = res[0][0]+res[0][1]+res[0][2]+res[0][3]res = res % GLOBAL_MODreturn resdef matrixpower(self, power):# res初始值為單位矩陣res = [[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 1, 0],[0, 0, 0, 1]] base = [[2, 1, 2, 1],[0, 1, 2, 1],[0, 0, 1, 1],[0, 0, 0, 1]] # 這個(gè)是我們構(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 res while True:try:n = int(input())ans = Solution()print(ans.f(n))except:break

總結(jié)

以上是生活随笔為你收集整理的牛客14607 递推（矩阵快速幂构造）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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