企业网站建立策划书,有多人做网站是个人备案,域名怎么创建网站吗,链接生成器链接#xff1a;https://ac.nowcoder.com/acm/problem/18987 来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld
题目描述
qn是个特别可爱的小哥哥#xff0c…链接https://ac.nowcoder.com/acm/problem/18987 来源牛客网
时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld
题目描述
qn是个特别可爱的小哥哥qy是个特别好的小姐姐他们两个是一对好朋友 [ cp (划掉~) 又是一年嘤花烂漫时小qn于是就邀请了qy去嘤花盛开的地方去玩。当qy和qn来到了田野里时qy惊奇的发现嘤花花瓣以肉眼可见的速度从树上长了出来。 仔细看看的话花瓣实际上是以一定规律长出来的而且每次张成新的花瓣的时候上一次的花瓣就会都落到地上而且不会消失。 花瓣生长的规律是当次数大于等于2时第i次长出来的花瓣个数和上一次张出来的花瓣个数的差是斐波那契数列的第i-1项。初始的时候地上没有花瓣树上的花瓣个数为1第一次生长的花瓣个数为1。初始的那个花瓣就落到了地上 现在小qn想知道经过k次生长之后树上和地上的总花瓣个数是多少? ps:斐波那契数列: f[1]f[2]1;f[i]f[i-1]f[i-2] (i2且i ∈ N)
输入描述:
一行一个数k
输出描述:
一行一个数m表示第k次生长过后树上和地上的总花瓣数是多少。由于答案会很大请你将答案mod 998244353后输出 题意不难理解最终结果是要求斐波那契数列的前k1项之和 又因为Sn f(n2) - 1 所以最后就是求 f(n3)-1
普通的斐波那契数列求解可以用递归时间复杂度O(2^N)但是这里的数据太大会超时 所以这里用矩阵快速幂时间复杂度OlogN来求解。 [F(n),F(n-1)] [F(1), F(0)] * [[1 1] [1 0]]^(n-1)
F(n)的获取方法有两种
第一种是取矩阵运算结果的第一行第一列 由[F(n),F(n-1)] [F(1), F(0)] * [[1 1] [1 0]]^(n-1)得矩阵运算n-1次第二种取矩阵运算结果第一行元素之和 由[F(n-1),F(n-2)] [F(1), F(0)] * [[1 1] [1 0]]^(n-2), F(n) F(n-1)F(n-2),矩阵运算n-2次
GLOBAL_MOD 998244353
k int(input())
题意不难理解最终结果是要求斐波那契数列的前k1项之和 又因为Sn f(n2) - 1 所以最后就是求 f(n3)-1普通的斐波那契数列求解可以用递归时间复杂度O(2^N)但是这里的数据太大会超时
所以这里用矩阵快速幂时间复杂度OlogN来求解。[F(n),F(n-1)] [F(1), F(0)] * [[1 1] [1 0]]^(n-1)F(n)的获取方法有两种
第一种是取矩阵运算结果的第一行第一列
由[F(n),F(n-1)] [F(1), F(0)] * [[1 1] [1 0]]^(n-1)得矩阵运算n-1次
第二种取矩阵运算结果第一行元素之和
由[F(n-1),F(n-2)] [F(1), F(0)] * [[1 1] [1 0]]^(n-2), F(n) F(n-1)F(n-2),矩阵运算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]] # 这个是我们根据斐波那契数列的特点构造的矩阵 while power !0:if power1 !0:res self.multimatrix(res, base)power power1base 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(k3)))
