题目链接~~>
这题可以找规律也可以用矩阵乘法做。
矩阵解法:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
题意:给出一个递推公式,求第N项。
然后使用矩阵乘法时间复杂度为log(n)的一个算法。
代码:
#include<stdio.h>
struct M
{
int p[2][2] ; // 范围大的话用 long long
} ;
M mult(M a,M b)//矩阵相乘
{
int i,j,k ;
M c ;
for(i=0 ;i<2 ;i++)
for(j=0 ;j<2 ;j++)
{
c.p[i][j]=0 ;
......
阅读全文