首页 > 代码库 > UVA 10655 - Contemplation! Algebra(矩阵快速幂)
UVA 10655 - Contemplation! Algebra(矩阵快速幂)
UVA 10655 - Contemplation! Algebra
题目链接
题意:给定p, q, n代表p=a+b,q=ab求an+bn
思路:矩阵快速幂,公式变换一下得到(an+bn)(a+b)=an+1+bn+1+ab(an?1+bn?1),移项一下得到an+1+bn+1=(an+bn)p?q(an?1+bn?1)
这样就可以用矩阵快速幂求解了
代码:
#include <stdio.h> #include <string.h> long long p, q, n; struct mat { long long v[2][2]; mat() {memset(v, 0, sizeof(v));} mat operator * (mat c) { mat ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { ans.v[i][j] = ans.v[i][j] + v[i][k] * c.v[k][j]; } } } return ans; } }; mat pow_mod(mat x, long long k) { mat ans; ans.v[0][0] = ans.v[1][1] = 1; while (k) { if (k&1) ans = ans * x; x = x * x; k >>= 1; } return ans; } long long solve() { if (n == 0) return 2; if (n == 1) return p; if (n == 2) return p * p - 2 * q; mat a; a.v[0][0] = p; a.v[0][1] = -q; a.v[1][0] = 1; a = pow_mod(a, n - 2); return a.v[0][1] * p + a.v[0][0] * (p * p - 2 * q); } int main() { while (scanf("%lld%lld%lld", &p, &q, &n) == 3) { printf("%lld\n", solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。