本文主要是介绍Hdu 2256 Problem of Precision[矩阵快速幂 + 数学]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2256
题目的意思很简单粗暴。
简单思考一下，可以推出递推公式fi = fi-1 * a^2， a = sqrt(2) + sqrt(3)。
递推公式出来了，直接快速幂就好。。。但是， 我们发现10^9是很消耗精度， 可以肯定是很多的正确的做法，都是因为精度的问题而挂的。。。
思考无果后， 看了题解。。
表示还需要努力学习。。！！！
表示很吊。。。。构造5 - 2*sqrt(6)，是为了避免sqrt(6)所带来的精度。。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 4;
const int mod = 1023;
struct Matrix
{int n, m;int a[N][N];Matrix(){memset(a, 0, sizeof(a));}
}unit, A;Matrix operator *(Matrix a, Matrix b)
{Matrix ans;ans.n = a.n; ans.m = b.m;for(int i = 1; i <= a.n; i ++){for(int j = 1; j <= b.m; j ++){for(int k = 1; k <= b.n; k ++)ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) & mod;}}return ans ;
}int power(int k)
{Matrix ans = unit, B = A;while(k){if(k & 1) ans = ans * B;B = B * B;k = k >> 1;}return 2 * ans.a[1][1] - 1;
}int main()
{int T;scanf("%d", &T);while(T --){int n;scanf("%d", &n);unit.n = 1; unit.m = 2;unit.a[1][1] = 5; unit.a[1][2] = 2;A.n = 2; A.m = 2;A.a[1][1] = 5; A.a[1][2] = 2; A.a[2][1] = 12; A.a[2][2] = 5;printf("%d\n", power(n - 1) & mod);}return 0;
}
期间，见到了一个 &1023的位运算。。
其实 x & 1023 = x % 1024。。这样的形式是第一次见，表示很好很强大。。
这种形式只使用于 mod = 2 ^ n - 1。为什么？？我想不用解释。。。
这篇关于Hdu 2256 Problem of Precision[矩阵快速幂 + 数学]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
