我正在试着解决这个问题: SPOJ problem。经过一些研究,我发现这其实可以归结为计算第n个斐波那契数的简单运算,但是n可能会非常大,所以O(n)解法并不好用。在Google上搜索后,我发现可以用O(logn)的时间复杂度计算第n个斐波那契数,而且还找到了一个完成该运算的代码示例:
long long fibonacci(int n) {
long long fib[2][2] = {{1,1},{1,0}}, ret[2][2] = {{1,0},{0,1}}, tmp[2][2] = {{0,0},{0,0}};
int i, j, k;
while (n) {
if (n & 1) {
memset(tmp, 0, sizeof tmp);
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
for (k = 0; k < 2; k++)
tmp[i][j] = (tmp[i][j] + ret[i][k] * fib[k][j]);
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
ret[i][j] = tmp[i][j];
}
memset(tmp, 0, sizeof tmp);
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
for (k = 0; k < 2; k++)
tmp[i][j] = (tmp[i][j] + fib[i][k] * fib[k][j]);
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
fib[i][j] = tmp[i][j];
n /= 2;
}
return (ret[0][1]);
}
我尝试修改了代码,但是仍然得到 WA 错误:http://ideone.com/3TtE5m
我是不是在计算模运算时出了错?还是有其他问题?