斐波拉契数列IV【矩阵乘法】

题目大意：

题目链接：http://10.156.17.250/JudgeOnline/showproblem?problem_id=1531（学校局域网）

题目图片链接

求f[n]=f[n−1]+f[n−2]+n+1,f[1]=f[2]=1$f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1$

---

思路：

有四个元素，要

原来的元素	变成的元素
f[i−2]$f[i-2]$	f[i−1]$f[i-1]$
f[i−1]$f[i-1]$	f[i]$f[i]$
i$i$	i+1$i+1$
1$1$	1$1$

那么就可以求出矩阵a$a$

↑图片来自同学XXY
↑↑图片来自同学XXY
↑↑↑图片来自同学XXY
重要的事情说三遍
那么初始化出原来n=1,n=2$n=1,n=2$，直接往下求即可。

---

代码：

#include <cstdio>
#include <cstring>
#define MOD 9973
using namespace std;

int n,f[5];
int a[5][5]=
{
    {0,0,0,0,0},
    {0,0,1,0,0},
    {0,1,1,0,0},
    {0,0,1,1,0},
    {0,0,1,1,1}  
};

void mul(int f[5],int a[5][5])
{
    int c[5];
    memset(c,0,sizeof(c));
    for (int i=1;i<=4;i++)
     for (int j=1;j<=4;j++)
      c[i]=(c[i]+f[j]*a[j][i])%MOD;
    memcpy(f,c,sizeof(c));
}

void mulself(int a[5][5])
{
    int c[5][5];
    memset(c,0,sizeof(c));
    for (int i=1;i<=4;i++)
     for (int j=1;j<=4;j++)
      for (int k=1;k<=4;k++)
       c[i][j]=(c[i][j]+a[i][k]*a[k][j])%MOD;
    memcpy(a,c,sizeof(c));
}

int main()
{
    scanf("%d",&n);
    if (n<3)
    {
        printf("1");
        return 0;
    }
    n-=2;
    f[1]=1;
    f[2]=1;
    f[3]=3;
    f[4]=1;
    for (;n;n>>=1)
    {
        if (n&1) mul(f,a);
        mulself(a);
    }
    printf("%d\n",f[2]%MOD);
    return 0;
}