我用C++的map<int,vector>去计算斐波那契，卡在11808位算不了，难受。

这是一个题Fibonacci Again     

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).     Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).       Print the word "yes" if 3 divide evenly into F(n).   Print the word "no" if not.

鄙人知道有规律（n-2）%4==0就YES;但还是想用迭代做一下；

迭代函数到11808就算不了了（用二分凑出来的），查了查map,vector的容量也没超啊（学生党哭哭）

#include<bits/stdc++.h>
#define V vector<int>
using namespace std;
map<int,V> fi;
V add(V &A,V &B);
int num;
V Fibonacci(int n){
	if(n==0)return fi[0];//f(0)=7
	if(n==1)return fi[1];//f(1)=11
	if(fi[n].size()!=0)return fi[n];//存进map里
	//cout<<num++<<endl;
	 Fibonacci(n-1);//递归运算第一个
	 Fibonacci(n-2);//递归运算第二个

	return fi[n]=add(fi[n-1],fi[n-2]);//相加
}
int main(){
	fi[0].push_back(7);
	fi[1].push_back(11);
	Fibonacci(11807); //11808就不行
	//for(int i=0;i<10000;i++){
		 
		//for(int j=fi[11807].size()-1;j>=0;j--)cout<<fi[11807][j];
	//}
	int n;
	while(scanf("%d",&n)!=EOF){
		int sum=0;
		for(int i=fi[n].size()-1;i>=0;i--)sum+=fi[n][i];
		if(sum%3==0)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
V add(V &A,V &B){//高进度A+B 
	V C;
	int t=0;
	for(int i=0;i<A.size()||i<B.size();i++){
		if(i<A.size())t+=A[i];
		if(i<B.size())t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)C.push_back(1);
	return C;
}

首先....你用递归去算这么大的工作量明显不现实, 非常耗时间, 这时候dp快很多

其次....别说int, 我怀疑long long都不够用....建议写string大数模板....

你知道11801是多大了吗？

不知道，反正我用vs2017一运行就报错了。应该是数值计算太大了，超出范围了吧！

您好，我是问答小助手，看到您的问题已被解答，欢迎您加入CSDN！

目前问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632