首页 > 其他分享 >Fib数列的递推

Fib数列的递推

时间:2023-04-30 18:34:26浏览次数:34  
标签:数列 int long Fib mod include 递推 matrix

 

矩阵快速幂

 

#include <iostream>
 #include <cmath>
 #include <algorithm>
 using namespace std; 
 #define N 2
  int mod;
 
 
 #define int long long
  struct matrix {
  	int a[N+2][N+2];
  };
  matrix m1; 
  int n;
  
  void init_(matrix &x){
  	
  	int i,j;
  	for(i=1;i<=2;i++)
  	 for(j=1;j<=2;j++) {
  	 	 x.a[i][j]=0;
  	 	 if(i==j) x.a[i][j]=1;
  	 }
  }
  matrix mul(matrix &x,matrix &y){
 	int i,j,k;
 	matrix z;
 	
 	for(i=1;i<=2;i++)
 	 for(j=1;j<=2;j++){
 	 	z.a[i][j]=0;
 	 	for(k=1;k<=2;k++)
 	 	 z.a[i][j]+=x.a[i][k]*y.a[k][j], z.a[i][j]%=mod;
 	 }
 	
 	return z;
 }
   matrix ksm(matrix &x,int k){
 	matrix tmp=x, ans;
 	init_(ans);
 	
 	while(k){
 		if(k&1) ans=mul(ans,tmp);
 		
 		tmp=mul(tmp,tmp); 
 		k/=2;
 	}
 	return ans;
 }
 
  signed main(){
 	std::ios::sync_with_stdio(0);
 	cin>>n>>mod;
 	
 	for(int i=1;i<=N;i++)
 	 for(int j=1;j<=N;j++) m1.a[i][j]=1;
 	 m1.a[2][2]=0;
 	 
 	 if(n<=2){ 
 	 	cout<<1<<endl; return 0;
 	 }
 	 
 	 matrix ans =ksm(m1,n-2);
 	 cout<<(ans.a[1][1]+ans.a[2][1])%mod<<endl;
 	 
  }

 

标签:数列,int,long,Fib,mod,include,递推,matrix
From: https://www.cnblogs.com/towboa/p/17365580.html

相关文章

  • Python 斐波那契数列
    概念:斐波那契数列又称黄金分割数列,即:1,1,2,3,5,8,13,21,…,这个数列前两项都是1,从第3项开始,每一项都等于前两项之和。随着数列的增加,前一项与后一项的比值逼近0.6180339887这个黄金分割系数 code:deffiblist(input):fib=[1,1]#第一和第二项固定为值为1......
  • 连续数列和问题
    关于7的迷题Description给你n个数,分别是a[1],a[2],...,a[n]。求一个最长的区间[x,y],使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间,输出0。FormatInput第一行给出数字N,1≤N≤50,000接下来N个数字,值在[0…1,000,000]......
  • [NOI2005] 维护数列
    总体思路其实跟用线段树维护区间最大字段和差不多,不过唯一麻烦的地方在于要算上自己。然后我们可以开一个队列来回收那些被delete的点,这样可以节省空间,特别需要注意的是release的时候,标记什么的一定记得清空。本来insert我是直接一个个merge的,这样就会导致特别慢,因此我们可以借......
  • 实战案例 | 双束聚焦离子束(DB-FIB)和透射电子显微镜(TEM)在芯片失效分析中的组合应用
    在做HTGB(高温栅偏测试)项目时,出现了Passdie漏电较小,FaildieIGSS漏电过大(>200nA)的情况。需要对漏电大的芯片进行复测,同时定位漏电所在的位置(热点Hotspot)。之后再利用FIB/TEM对漏电位置进行微观结构/成分分析,找到漏电点所在的膜层;最后基于电镜分析的结果对失效机理做初步判断......
  • #yyds干货盘点# LeetCode程序员面试金典:外观数列
    题目:给定一个正整数n,输出外观数列的第n项。「外观数列」是一个整数序列,从数字1开始,序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列:countAndSay(1)="1"countAndSay(n)是对countAndSay(n-1)的描述,然后转换成另一个数字字符串。前五项......
  • 剑指 Offer 10- I. 斐波那契数列
     分析:偷个懒,上次做的一样的题代码:1classSolution(object):2deffib(self,n):3"""4:typen:int5:rtype:int6"""7ifn<2:8returnn9f=[0foriinra......
  • 兔子数列
    有一对兔子,从出生后的第三个月起,每个月生一对小兔子,假设所有的兔子都不死亡,30个月后会有多少兔子?分析:此问题是数学中著名的兔子数列问题(斐波那契数列),1,1,2,3,5.........其通式为:n=n-1+n-2;由此可以写出代码。#include<stdio.h>intmain(){ inti,f,f1=1,f2=1; printf("%d,%d",f1,......
  • 斐波那契数列
    斐波那契数列 公式:F(n)=F(n-1)+F(n-2)  步骤: 1、初始化:第0项为0,第1项为1if(n<=1){  returnn;} 2、设置参数,确保第二项也为1intres=0;inta=0;intb=1; 3、从2开始循环到n,把自己的值赋给下一项for(inti=2;i<=n;i++){  res=a+......
  • 03 | 写一个能产生斐波那契数列的range——惰性求值
    1.首先为了满足range概念的要求我们需要提供begin()和end()2.begin()和end()返回的应该是迭代器,注意这个地方两种可以返回两种不同类型(c++17后即可)3.为了满足迭代器概念的要求我们提供5个typedef,并根据std::input_iterator_tag类型决定我们要实现的“解引用函数”,......
  • 斐波拉契数列
    古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 先写出来前几个月的兔子数,分别是1、1、2、3、5、8、13、21、34......就是这样一组数列,第三个数是前两个数的和,也就是n=(n-1)+(n-2) ......