首页 > 其他分享 >Fibonacci 第 n 项

Fibonacci 第 n 项

时间:2024-08-30 15:51:35浏览次数:9  
标签:tmp int long Fibonacci RC sizeof ret

// Fibonacci 第 n 项.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://loj.ac/p/10220

题目描述
大家都知道 Fibonacci 数列吧,f_1=1,f_2=1,f_3=2,f_4=3,~~~,f_n=f_{n-1}+f_{n-2}。

现在问题很简单,输入 n 和 m,求 f_n  mod m。

输入格式
输入 n,m。

输出格式
输出 f_n mod m。

样例
输入
5 1000
输出
5
数据范围与提示
对于 100\% 的数据, 1<= n <= 2* 10^9, 1<= m <= 10^9+10。
*/

#include <iostream>
#include <cstring>

using namespace std;

long long n, m;

long long A[2] = { 1,1 };
long long B[2][2] = {
	{0,1},
	{1,1},
};
long long R[2] = { 0,0 };


void mul(long long Z[2], long long X[2], long long Y[2][2]) {
	memset(Z, 0, sizeof(Z)*2);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			Z[i] += X[j] * Y[j][i];
			Z[i] %= m;
		}
	}
}

void mul(long long  ret[2][2], long long  X[2][2], long long  Y[2][2]) {
	memset(ret, 0, sizeof(ret[0][0]) * 2 * 2);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				ret[i][j] += X[i][k] * Y[k][j];
				ret[i][j]   %= m;
			}
		}
	}
}


void mulrep(long long X[2][2], long long q) {
	long long tmp[2][2]; memset(tmp, 0, sizeof tmp);
	long long R[2][2]; memset(R, 0, sizeof R);
	for (int i = 0; i < 2; i++) { R[i][i] = 1; }
	long long RC[2][2]; memcpy(RC, R, sizeof RC);
	while (q != 0) {
		if (q & 1) {
			memcpy(RC, R, sizeof RC);
			mul(R, RC,X);
		}
		q >>= 1;
		mul(tmp,X,X);
		memcpy(X, tmp, sizeof tmp);
	}

	memcpy(X, R, sizeof R);
}


int main()
{	
	cin >> n;
	m = 1e9 + 7;
	mulrep(B, n -1);
	long long ret[2];
	mul(ret,A,B);
	
	cout << ret[0] <<  endl;
	
	return 0;
}

标签:tmp,int,long,Fibonacci,RC,sizeof,ret
From: https://www.cnblogs.com/itdef/p/18388863

相关文章

  • 实验6-9 使用函数输出指定范围内的Fibonacci数
    本题要求实现一个计算Fibonacci数的简单函数,并利用其实现另一个函数,输出两正整数m和n(0<m≤n≤10000)之间的所有Fibonacci数。所谓Fibonacci数列就是满足任一项数字是前两项的和(最开始两项均定义为1)的数列。函数接口定义:intfib(intn);voidPrintFN(intm,intn);......
  • 编写并测试Fibonacci()函数,该函数用循环替代递归计算斐波那契数
    /编写并测试Fibonacci()函数,该函数用循环替代递归计算斐波那契数斐波那契数列(FibonacciSequence)又称黄金分割数列。特别指出:第0项是0,第1项是第一个1。此数列从第2项开始,每一项都等于前两项之和。/include<stdio.h>intFibonacci(intn){//使用循环计算斐波那契数inta=0,b......
  • CF1634F Fibonacci Additions 题解
    CF1634FFibonacciAdditions题解传送门。题目大意:给定两个序列\(A\)和\(B\),每次一个可以选一个区间,并在区间的第\(i\)个数加上\(F_i\),其中\(F\)是斐波那契数列,你需要在每次询问结束时输出两个序列是否相等。可以先求一个序列\(C\)表示\(A\)和\(B\)每个位置的......
  • 1143 多少个Fibonacci数
    首先,我们需要生成一个Fibonacci数列,直到其值超过10^100。由于Fibonacci数列的性质,我们知道这个数列的长度不会超过500。然后,对于每一对输入的a和b,我们在生成的Fibonacci数列中查找在a和b之间的数的个数。这可以通过二分查找来实现,因为Fibonacci数列是有序的。以下是对应的C+......
  • square869120Contest #3 G Sum of Fibonacci Sequence
    洛谷传送门AtCoder传送门特判\(n=1\)。将\(n,m\)都减\(1\),答案即为\[[x^m]\frac{1}{(1-x-x^2)(1-x)^n}\]若能把这个分式拆成\(\frac{A(x)}{(1-x)^n}+\frac{B(x)}{1-x-x^2}\)的形式,其中\(\degA(x)\len-1,\degB(x)\le1\),那么答案就是好算的。......
  • POI2012ROZ-Fibonacci Representation
    POI#Year2012#数学贪心的每次选择最接近的两个数,\(x=min(x-fib_{i-1},fib_i-x)\)//Author:xiaruizeconstintN=2e5+10;vector<int>vec;intn;voidsolve(){ intres=0; cin>>n; while(n) { autoit=upper_bound(ALL(vec),n); n=min(n-(......
  • CF1634F Fibonacci Additions
    Statement:给出两个长度为\(n\)的序列\(a,b\),每次在\(a\)或\(b\)上\([l,r]\)操作,一次操作将会使\([l,r]\)中的数分别加上\(fib[1],fib[2]...,fib[r-l+1]\),每次操作完询问\(a,b\)是否在模\(mod\)意义下相等。Solution:先简化问题,令\(c_i=a_i-b_i\),问题......
  • 6-1 使用函数输出指定范围内Fibonacci数的个数
    本题要求实现一个计算Fibonacci数的简单函数,并利用其实现另一个函数,输出两正整数m和n(0<m<n≤100000)之间的所有Fibonacci数的数目。所谓Fibonacci数列就是满足任一项数字是前两项的和(最开始两项均定义为1)的数列,fib(0)=fib(1)=1。其中函数fib(n)须返回第n项Fibonacci数;函数Prin......
  • 蓝桥杯 试题 基础练习 Fibonacci数列
    问题描述Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。输入格式输入包含一个整数n。输出格式输出一行,包含一个整数,表示Fn除以10007的余数。说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要......
  • QOJ #1280.Fibonacci Partition/Fibonacci性质大杂烩
    QOJ#1280.FibonacciPartition(为什么布置的作业题没有任何可见AC记录啊/kk)拿下了QOJ上的用户首杀(同时目前也是QOJ可见的submission中唯一一个过掉这个题的,另一个是vjudge上我的提交)。也许是这个题实在是太冷门了,但是从Fibonacci-Lucas数列的性质应用上是一道非常......