HDU-1005-（Number Sequence）

解题思路

1.DP基础题目，根据动态转移方程，推导结果

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

解题遇到的问题

1.逐步去求n，会存在超时问题，因为n如果是一亿次，就得求一亿次，通过分析题意可知，fn的值实际存在循环， (A * f(n - 1) + B * f(n - 2)) mod 7.，所以总共是7*7=49

后续需要总结学习的知识点

无

##解法1
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner mScanner = new Scanner(System.in);
        // (1 <= A, B <= 1000, 1 <= n <= 100,000,000)
        // f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
        while (true) {
            int a = mScanner.nextInt();
            int b = mScanner.nextInt();
            long n = mScanner.nextLong();
            if (a == 0 && b == 0 && n == 0) {
                break;
            }

            long ans = 1;
            if (n != 1 && n != 2) {
                long f1 = 1;
                long f2 = 1;
                for (int i = 3; i <= n % 49; i++) {
                    ans = (a * f1 + b * f2) % 7;
                    f2 = f1;
                    f1 = ans;
                }
            }
            System.out.println(ans);
        }
        mScanner.close();
    }
}