acm题中的小问题“f(1) = 1,f(2) = 1,f(n) = (A * f(n - 1) +

网友回答

这个题目是有周期的,因为是在7里面,所以所有的组合最多是7*7,也就是周期不超过49,还可以使用矩阵乘法
[A B] [f[2]]
[0 1] [f[1]]
这样乘一次就可以得到
[f[3]]
[f[2]]
再乘一次就可以得到下一组数字,
[A B]^(n-2) [f[2]]
[0 1] [f[1]]
这样就可以[f[n]]
[f[n-1]]
下面这个式子可以用log(n)次的矩阵乘法求出,对于n=100000000只要计算20多次
[A B]^(n-2)
[0 1] #include
void multi(int sum[][2],int matrix[][2])
{int i,j,c[2][2],k;
for(i=0;i