首页 > 代码库 > HDU2256-Problem of Precision(矩阵构造+快速幂)
HDU2256-Problem of Precision(矩阵构造+快速幂)
题目链接
题意:求sqrt(sqrt(2) + sqrt(3)) ^ 2n MOD 1024
思路:
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int MOD = 1024; int n; struct mat { int s[2][2]; mat(int a = 0, int b = 0, int c = 0, int d = 0) { s[0][0] = a; s[0][1] = b; s[1][0] = c; s[1][1] = d; } mat operator * (const mat& c) { mat ans; sizeof(ans.s, 0, sizeof(ans.s)); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) ans.s[i][j] = (ans.s[i][j] + s[i][k] * c.s[k][j]) % MOD; return ans; } }tmp(5, 12, 2, 5); mat pow_mod(int k) { if (k == 1) return tmp; mat a = pow_mod(k / 2); mat ans = a * a; if (k % 2) ans = ans * tmp; return ans; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); mat ans = pow_mod(n); printf("%d\n", (ans.s[0][0] * 2 - 1) % MOD); } return 0; }
HDU2256-Problem of Precision(矩阵构造+快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。