HDU 4565 So Easy! 矩阵快速幂

题意：

求(S_n=left lceil (a+sqrt{b})^n ight ceil mod \, m)的值。

分析：

设((a+sqrt{b})^n=A_n+B_n sqrt{b})，
((a+sqrt{b})^{n+1}=(a+sqrt{b})(A_n+B_n sqrt{b})=(aB_n+A_n)+(A_n+aB_n) sqrt{b})，
所以有转移矩阵：
$egin{bmatrix}
a & b
1 & a
end{bmatrix}
egin{bmatrix}
A_n
B_n
end{bmatrix}

egin{bmatrix}
A_{n+1}
B_{n+1}
end{bmatrix}$

如果把(sqrt{b})变为(-sqrt{b})，就得到((a- sqrt{b})^n=A_n-B_n sqrt{b})。
两式相加：((a+sqrt{b})^n+(a-sqrt{b})^n=2A_n)。
再由题中所给条件知道，(a-sqrt{b})是个小于(1)的数，所以(left lceil (a+sqrt{b})^n ight ceil=2A_n)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b, n, m;

int mul(int a, int b) { return a * b % m; }

void add(int& a, int b) { a += b; if(a >= m) a -= m; }

struct Matrix
{
	int a[2][2];

	Matrix() { memset(a, 0, sizeof(a)); }

	Matrix operator * (const Matrix& t) const {
		Matrix ans;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					add(ans.a[i][j], mul(a[i][k], t.a[k][j]));
		return ans;
	}
};

Matrix pow_mod(Matrix a, int p) {
	Matrix ans;
	for(int i = 0; i < 2; i++) ans.a[i][i] = 1;
	while(p) {
		if(p & 1) ans = ans * a;
		a = a * a;
		p >>= 1;
	}
	return ans;
}

int main()
{
	while(scanf("%d%d%d%d", &a, &b, &n, &m) == 4) {
		a %= m; b %= m;
		Matrix M;
		M.a[0][0] = a; M.a[0][1] = b;
		M.a[1][0] = 1; M.a[1][1] = a;
		M = pow_mod(M, n - 1);
		int ans = 0;
		add(ans, mul(M.a[0][0], a));
		add(ans, M.a[0][1]);
		ans = mul(ans, 2);
		printf("%d
", ans);
	}

	return 0;
}