HDU1005 Number Sequence 矩阵快速幂

HDU1005：Number Sequence
数字快速幂问题：

最后问题转化为求矩阵：

• 矩阵快速幂只会运用在方阵中。
• 题目中给出f(n)由f(n-1)和f(n-2)推得。
• 详细构造矩阵可以参考：https://blog.csdn.net/acmdream/article/details/18137551

import java.util.Scanner;

class S {// i行j列的矩阵数组
	int i, j;
	long[][] sz;

	public S(int i, int j) {
		this.i = i;
		this.j = j;
		sz = new long[i][j];
	}
}

public class Main {
	static long mod = (long) 7;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int a = in.nextInt();
			int b = in.nextInt();
			int n = in.nextInt();
			if (a == 0 && b == 0 && n == 0)
				break;
			if (n < 3)
				System.out.println(1);
			else {
				S A = new S(2, 2);// 实例化矩阵类
				A.sz[0][0] = a;
				A.sz[0][1] = b;
				A.sz[1][0] = 1;
				A.sz[1][1] = 0;
				S ans = new S(2, 2);// 结果矩阵
				ans = pow2(A, n - 2);
				System.out.println((ans.sz[0][0] + ans.sz[0][1]) % mod);
			}

		}
	}

	private static S pow2(S a, long b) // 求矩阵a(方阵)的b次幂
	{
		S c = new S(a.i, a.j);
		for (int x = 0; x < a.i; x++)
			// 建立一个对角线均为1的矩阵
			c.sz[x][x] = 1;
		while (b != 0) {
			if ((b & 1) == 1) {
				c = mul(c, a);
			}
			a = mul(a, a);
			b >>= 1;
		}
		return c;
	}

	private static S mul(S A, S B) // A*B%mod
	{
		S C = new S(A.i, B.j);//
		for (int i = 0; i < A.i; i++) {// 枚举矩阵A的行
			for (int j = 0; j < B.j; j++) {// 枚举矩阵B的列
				for (int k = 0; k < A.j; k++) {// k代表矩阵A的列的同时代表举着B的行
					C.sz[i][j] += (A.sz[i][k] * B.sz[k][j]) % mod;
					C.sz[i][j] %= mod;
				}
			}
		}
		return C;
	}
}