HDU-1005 Number Sequence 题解

题目大意

定义一个等式$f(n)$.

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

输入A、B和n，求出$f(n)$.

解题思路

之前写这种题，一看就是有规律。

然后以49一循环，这题简单a了。。

但是其实是因为杭电数据太水了。。

附上别人的测试数据。

input

247 602 35363857
376 392 9671521
759 623 18545473
53 399 46626337
316 880 10470347
0 0 0

output

4
3
5
2
3

我的代码是过不了的。。

所以说这题正解应该是矩阵快速幂。

其实矩阵快速幂和快速幂差不多，就是把数字的乘法换成矩阵的乘法即可。

由题目可以得到$\begin{equation} \begin{array}{c c} \left( \begin{array}{ccc} f(3) \\ f(2) \\ \end{array} \right) & = \left( \begin{array}{ccc} a & b \\ 1 & 0 \\ \end{array} \right) & \left( \begin{array}{ccc} f(2)\\ f(1) \\ \end{array} \right) \end{array} \end{equation}$

$f(3)=a\times f(2)+b\times f(1)$.

将公式推广到n。

$\begin{equation} \begin{array}{c c} \left( \begin{array}{ccc} f(n) \\ f(n-1) \\ \end{array} \right) & = \left( \begin{array}{ccc} a & b \\ 1 & 0 \\ \end{array} \right)^{n-2} & \left( \begin{array}{ccc} f(2) \\ f(1) \\ \end{array} \right) \end{array} \end{equation}$

设$A = \left( \begin{array}{ccc} a & b \\ 1 & 0 \\ \end{array} \right)^{n-2}$

可以得到$f(n)=(A[0][0]+A[0][1])%7$。

所以关键就是要使用快速幂计算出A，即可得出答案。

补充：单位矩阵为对角线为1，其余都为0的矩阵。

完整代码

#include <iostream>
using namespace std;

typedef struct {
	int m[2][2];
}M;

void mul(M &a, M b) {
	M ans;
	ans.m[0][0] = ans.m[0][1] = ans.m[1][0] = ans.m[1][1] = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++)
				ans.m[i][j] += (a.m[i][k] * b.m[k][j])%7;
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			a.m[i][j] = ans.m[i][j]%7;
		}
	}
}

void qpow(M a, int n) {
	M ans;
	for (int i = 0; i < 2; i++) {//这里换成单位矩阵会更好，之前不知道。。
		for (int j = 0; j < 2; j++) {
			ans.m[i][j] = a.m[i][j] % 7;
		}
	}
	n--;
	while (n) {
		if (n & 1) mul(ans, a);
		n >>= 1;
		mul(a, a);
	}
	cout << (ans.m[0][1] + ans.m[0][0]) % 7 << endl;
}

int main() {
	M m;
	int a, b, n;
	while (cin >> a >> b >> n && a || b || n) {
		if (n <= 2) {
			cout << 1 << endl;
			continue;
		}
		m.m[0][0] = a;
		m.m[0][1] = b;
		m.m[1][0] = 1;
		m.m[1][1] = 0;
		qpow(m, n-2);
	}
}