(ACM系列之一)从简单开始

唉，太复杂了，没看懂啥意思。

还是用递归最简单，你说堆栈溢出？其实当然有办法解决啦！

递归转循环

public class AcmTest {
	
	public static int [] r; //也可以用简单的两个变量来存储f(n-1)和f(n-2)
	
	public static int a;
	
	public static int b;
	
	public static int n;
	
	public static void process(int n){
		if(n<3) {
			r[n] = 1;
			
			return;
		}
		
		r[n] = (a * r[n-1] + b * r[n-2]) % 7;
	}
	
	public static int calculate(int n, int a, int b){
		r = new int[n + 1];
		AcmTest.a = a;
		AcmTest.b = b;
		for (int i = 1; i <= n; i++) {
			process(i);			
		}
		
		return r[n];
		
	}
	
	public static void main(String args[]){
		int a = 2;
		int b = 2;
		//for (int i = 1; i <= 10000; i++) {
		//	System.out.println(calculate(i,a,b));
		//}
		System.out.println(calculate(3002,a,b));
	}
}

第2版本：

public class AcmTest {
	
	public static int fp1; // 存储 f(n-1)
	
	public static int fp2; // 存储 f(n-2)
	
	public static int a;
	
	public static int b;
	
	public static void process(int n){
		
		if(n<3) {
			fp2 = fp1;
			fp1 = 1;
			return;
		}
		
		int tmp = (a * fp1 + b * fp2) % 7;
		fp2 = fp1;
		fp1 = tmp;
	}
	
	public static int calculate(int n, int a, int b){
		fp1 = 0;
		fp2 = 0;
		AcmTest.a = a;
		AcmTest.b = b;
		for (int i = 1; i <= n; i++) {
			process(i);			
		}
		
		return fp1;
		
	}
	
	public static void main(String args[]){
		int a = 2;
		int b = 2;
		for (int i = 1; i <= 10; i++) {
			System.out.println(calculate(i,a,b));
		}
		System.out.println(calculate(3002,a,b));
	}
}

f(n) = A * f(n - 1) + B * f(n - 2)，给定f1,f2

广义斐波拉契，直接能求出来通项公式。
1、先化成1阶递推
另 α,β为 x^2=A*x+B的两个根，β>α,
则f(n+2)+β*f(n+1)=α*(f(n+1)+β*f(n))=....=α^n*(f2+β*f1)
另 D=f2+β*f1，则
f(n+2)-β^n*f2=D*(β^n-β^(n-1)*α+ ... β*α^(n-1)
另t=α/β,
f(n+2) = β^n*D*(1-(-t)^n)/(1+t) + -β^n*f2

等式右边全是已知数，直接能求出来f(n+2)
为了简化计算，计算右边的值的每一步，都先Mod 7再计算即可。

离散、组合数学，或者数论、不定方程/连分数里会涉及这些

在ACM世界里，这道题属于弱智题的行列，竟让这么多人望而生畏，都是培训惹的祸。。。

囧，看了讨论，估计TLE一片啊，还是kimmking正解

当n的达到几万亿或者更大的程度的时候，你这段求解代码是非常低效的；而实际上这个递推问题可以用矩阵算法来求解，时间复杂度可以降到O(log2 n)

是有这么一个公式，但是把n代入这个公式后要求式子的值似乎也有难度

好东西，lz估计精通算法的程序员还是挺少的，比如我，我需要这些帖！