2012-06-17 17:30:27Morris
[UVA][矩陣] 10229 - Modular Fibonacci
| Problem A: Modular Fibonacci |
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 7 11 6
Sample Output
89 25
#include <stdio.h>
struct M {
long long v[2][2];
} I = {1,0,0,1}, o = {0,0,0,0}, A = {1,1,1,0};
void mult(M &a, M &b, int m) {
static int i, j, k;
M t = o;
for(i = 0; i < 2; i++) {
for(j = 0; j < 2; j++) {
for(k = 0; k < 2; k++) {
t.v[i][j] += a.v[i][k]*b.v[k][j];
t.v[i][j] &= (1<<m)-1;
}
}
}
a = t;
}
void calc(int n, int m) {
M x = I, y = A;
while(n) {
if(n&1) mult(x, y, m);
mult(y, y, m);
n /= 2;
}
printf("%lld\n", x.v[0][2]);
}
int main() {
int n, m;
while(~scanf("%d %d", &n, &m))
calc(n, m);
return 0;
}