UVa 10229 Modular Fibonacci：矩阵快速幂求斐波那契

UVa 10229 Modular Fibonacci：矩阵快速幂求斐波那契2014-07-29

10229 - Modular Fibonacci

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1170

The Fibonacci numbers （0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...） are defined by the recurrence:

F0 = 0 F1 = 1 Fi = Fi-1 + Fi-2 for i>1

Write a program which calculates Mn = Fn mod 2m for given pair of n and m. 0< =n< =2147483647 and 0<=m< 20. Note that a mod b gives the remainder when a is divided by b.

Input and Output

Input consists of several lines specifying a pair of n and m. Output should be corresponding Mn, one per line.

Sample Input

11 711 6

Sample Output

思路：

如上图，使用矩阵快速幂搞定。

注意：（1<<19）^2会超int，所以要用long long

完整代码：

/*0.015s*/ #include<cstdio>#include<cstring>typedef long long ll; ll mod; struct mat{ll v[2][2];mat（）{memset（v, 0, sizeof（v））;}} m1; mat operator * （mat a, mat b）{mat c;for （int i = 0; i < 2; i++）for （int j = 0; j < 2; j++）for （int k = 0; k < 2; k++）c.v[i][j] = （c.v[i][j] + a.v[i][k] * b.v[k][j]） % mod;return c;} inline mat quickpow（mat a, int k）{mat b;b.v[0][0] = b.v[1][1] = 1;while （k）{if （k & 1）b = b * a;k >>= 1;a = a * a;}return b;} int main（）{m1.v[0][0] = m1.v[0][1] = m1.v[1][0] = 1, m1.v[1][1] = 0;int n, m;while （~scanf（"%d%d", &n, &m））{if （n == 0 || m == 0） puts（"0"）;else{mod = 1 << m;printf（"%d
", quickpow（m1, n - 1）.v[0][0]）;}}return 0;}