求助,正常递推+滚动数组才70诶
查看原帖
求助,正常递推+滚动数组才70诶
724988
hjqhs楼主2023/1/2 17:31
#include<bits/stdc++.h>
using namespace std;
int fib[3];
#define MOD 1000000007
int main(){
	int n;
	cin >> n;
	fib[1] = 1;
	fib[2] = 1;
	if(n == 1){cout << 1; return 0;}
	if(n == 2){cout << 1; return 0;}
	if(n == 3){cout << 2; return 0;}
	if(n == 4){cout << 3; return 0;}
	int hn = n / 2 + 1;
	int sn = n % 2;
	for(int i = 1; i <= hn - 2; i++){
		fib[1] = (fib[1] + fib[2]) % MOD;
		fib[2] = (fib[1] + fib[2]) % MOD;
	}
	if(sn == 1){
		fib[1] = (fib[1] + fib[2]) % MOD;
		cout << fib[1];
		return 0;
	}
	if(sn == 0){
		cout << fib[2] % MOD;
		return 0;
	}
	return 0;
} 
2023/1/2 17:31
加载中...