hdu 2256(矩阵快速幂)

2019-04-14 19:36发布

站内文章 / 模拟电子
11195 0 1769
题意：求(根号2 + 根号3)^2n模1024。
题解：浮点数无法精确模1024得到答案，下图是推导过程
这里写图片描述
根据推导过程得出解很简单了。 #include #include #include const int N = 3; struct Mat { int g[N][N]; }ori, res; int n; Mat multiply(Mat x, Mat y) { Mat temp; memset(temp.g, 0, sizeof(temp.g)); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % 1024; return temp; } void calc(int n) { while (n) { if (n & 1) res = multiply(ori, res); n >>= 1; ori = multiply(ori, ori); } } int main() { int t; scanf("%d", &t); while (t--) { memset(res.g, 0, sizeof(res.g)); scanf("%d", &n); ori.g[0][0] = ori.g[1][1] = 5; ori.g[0][1] = 12; ori.g[1][0] = 2; res.g[0][0] = 1; calc(n); printf("%d ", (res.g[0][0] * 2 - 1) % 1024); } return 0; }

热门文章