2013长沙市邀请赛 HDU 4565 So Easy!(矩阵快速幂）

2013长沙邀请赛 HDU 4565 So Easy!(矩阵快速幂）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4565

矩阵快速幂，要推公式。

参考了网上的题解，简直屌

    

代码：

#include <stdio.h>
#include <string.h>
#include <math.h>

long long a, b, n, m;

struct mat {
    long long v[2][2];
    mat() {
	memset(v, 0, sizeof(v));
    }
    mat operator * (mat a) {
	mat c;
	for (int i = 0; i < 2; i++)
	    for (int j = 0; j < 2; j++)
		for (int k = 0; k < 2; k++) {
		    c.v[i][j] = ((c.v[i][j] + v[i][k] * a.v[k][j]) % m + m) % m;
		}
	return c;
    }
};

mat pow_mod(mat a, long long k) {
    if (k <= 1) return a;
    mat ans = pow_mod(a * a, k / 2); 
    if (k&1) ans = ans * a;
    return ans;
}

int main() {
    while (~scanf("%lld%lld%lld%lld", &a, &b, &n, &m)) {
	mat s;
	s.v[0][0] = 2 * a; s.v[0][1] = -(a * a - b);
	s.v[1][0] = 1; s.v[1][1] = 0;
	long long c1 = (long long)(ceil(a + sqrt(b))) % m;
	long long c2 = (long long)(ceil((a + sqrt(b)) * (a + sqrt(b)))) % m;
	if (n == 1) printf("%lld\n", c1);
	else if (n == 2) printf("%lld\n", c2);
	else {
	    mat ans = pow_mod(s, n - 2);
	    printf("%lld\n", (((((ans.v[0][0] * c2 % m) + m) % m) + (((ans.v[0][1] * c1 % m) + m) % m)) + m) % m);
	}
    }
    return 0;
}