Modular Fibonacci
The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are de?ned 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
Input consists of several lines specifying a pair of n and m.
Output
Output should be corresponding Mn, one per line.
Sample Input
11 7
11 6
Sample Output
89
25
题解：
由于n<=2 147 483 647，直接for会超时。用矩阵快速幂就好了
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std ; typedef long long ll; ll MOD; struct Matrix { ll mat[2][2]; }U,F; Matrix multi (Matrix a, Matrix b) { Matrix ans; for(int i = 0; i < 2; i++) { for(int j = 0; j < 2; j++) { ans.mat[i][j] = 0; for(int k = 0; k < 2; k++) ans.mat[i][j] += a.mat[i][k] * b.mat[k][j]; ans.mat[i][j] %= MOD; } } return ans; } Matrix powss(ll n) { Matrix ans = U,p = F; while(n) { if(n&1) ans = multi(ans,p); n>>=1; p = multi(p,p); } return ans; } int main() { U = {1,0,0,1}; F = {1,1,1,0}; ll n,m; while(~scanf("%lld%lld",&n,&m)) { MOD = 1ll<<m; Matrix ans = powss(n); printf("%lld\n",ans.mat[0][1]); } return 0; }
UVA - 10229 Modular Fibonacci 矩阵快速幂
原文：http://www.cnblogs.com/zxhl/p/5146858.html