• 这道题怪怪的 虽然说一开始反应是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)。这是解决超时和内存不够的办法。