HDU 2256 Problem of Precision （矩阵快速幂）

ACM

题目地址：HDU 2256 Problem of Precision

题意：
给出一个式子，求值。

分析：
推起来最后那步会比较难想。
具体过程见：

表示共轭只听说过复数的和图的...
这构题痕迹好明显...
跟基友开玩笑说：如果遇到这种题，推到Xn+Yn*sqrt(6)这步时，打表最多只能打到10就爆int了，这是输出正解和Xn，说不定眼神好能发现ans = Xn * 2 - 1呢。= =...<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CrT6wuujujwvcD4KPHByZSBjbGFzcz0="brush:java;">/* * Author: illuz * Blog: http://blog.csdn.net/hcbbt * File: 2256.cpp * Create Date: 2014-08-03 14:27:15 * Descripton: */ #include #include #include #include #include using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int SIZE = 3; // max size of the matrix const int MOD = 1024; struct Mat{ int n; ll v[SIZE][SIZE]; // value of matrix Mat(int _n = SIZE) { n = _n; memset(v, 0, sizeof(v)); } void init(ll _v) { repf (i, 0, n - 1) v[i][i] = _v; } void output() { repf (i, 0, n - 1) { repf (j, 0, n - 1) printf("%lld ", v[i][j]); puts(""); } puts(""); } } a, b; Mat operator * (Mat a, Mat b) { Mat c(a.n); repf (i, 0, a.n - 1) { repf (j, 0, a.n - 1) { c.v[i][j] = 0; repf (k, 0, a.n - 1) { c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD; c.v[i][j] %= MOD; } } } return c; } Mat operator ^ (Mat a, ll k) { Mat c(a.n); c.init(1); while (k) { if (k&1) c = c * a; a = a * a; k >>= 1; } return c; } void solve(int n) { Mat a(2); a.v[0][0] = 5; a.v[0][1] = 12; a.v[1][0] = 2; a.v[1][1] = 5; a = a ^ (n - 1); int xn = 5 * a.v[0][0] + 2 * a.v[0][1]; printf("%d\n", (xn * 2 - 1) % MOD); } int t, n; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); solve(n); } return 0; }