1005.Number Sequence

这道题怪怪的 虽然说一开始反应是DP（肯定会超时） 看了很多答案都是找规律 但改了以后 发现还是不能AC
最后把自己的东西改成跟答案一样就AC了
这道题的切入就是 %7 0123456

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int n = sc.nextInt();
			if (A == B && B == n && n == 0)
				System.exit(0);
			int[] arr = new int[50];
			arr[1] = 1;
			arr[2] = 1;
			for (int i = 3; i < 50; i++) {//一旦超时就会报错 采用50
				arr[i] = (A * arr[i - 1] + B * arr[i - 2]) % 7;
			}
			System.out.println(arr[n % 49]);
		}
	}
}

因为对于f(n)来说，当n>=2时候，f(n)只可能为0-6之间的数字。f[i]=(af[i-1]+bf[i-2])%7,如果能够在f(n)中能够找到他的循环周期的话，那么只要用f[(n-1)/T]]即可在数组f中找到其对应的值，其算法复杂度仅仅只有O(i)，这个i远远小于n。当这个n值越大，这种周期式的算法优势就越明显。
//注释：因为无论是多么优秀的算法，只要当 a、b、n中的n足够大时候，都不行，除非找到他的规律，
//         这样的话，计算一个周期T内f(n)的值即可解决问题。剩余的只要输出f[(n-1)/T]就行了
后来通过参考别人的代码发现是有规律的，最后是对7取余数，所以，f(n-1)，f(n-2)最多各有七种情况（0、1、2、3、4、5、6），所以f(n)最多有7*7=49种情况，所以从一开始到49可能不尽相同，但是从50开始则开始循环，f(50)=f(50%49)=f(1)。这是解决超时和内存不够的办法。