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 2^m 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
问题链接：UVA10229 Modular Fibonacci
问题简述：（略）
问题分析：
这是一个循环数列计算问题。
这个问题也可以用矩阵快速幂进行计算。
程序说明：（略）
题记：（略）
参考链接：（略）
AC的C++语言程序如下：
/* UVA10229 Modular Fibonacci */#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6;
LL fib[N + 1];void setfib(LL mod, LL cycle)
{fib[0] = 1 % mod;fib[1] = 1 % mod;for(LL i=2; i<=cycle; i++)fib[i] = (fib[i - 2] + fib[i - 1]) % mod;
}int main()
{LL n, m;while(cin >> n >> m) {LL mod = 1LL << m;LL cycle = mod * 3 / 2;setfib(mod, cycle);cout << fib[--n % cycle] << endl;}return 0;
}