这道题怪怪的 虽然说一开始反应是 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(50I)=f(1). 这是解决超时和内存不够的办法.
来源: http://www.bubuko.com/infodetail-3117353.html