题目描述：

数列 f [ n ] = f [ n − 1 ] + f [ n − 2 ] , f [ 1 ] = f [ 2 ] = 1 f[n]=f[n-1]+f[n-2],f[1]=f[2]=1 f[n]=f[n−1]+f[n−2],f[1]=f[2]=1的前 n n n项和 s [ n ] s[n] s[n]的快速求法

思路：

使 [ s n − 2 f n − 1 f n − 2 ] \begin{bmatrix}s_{n-2} & f_{n-1} & f_{n-2}\end{bmatrix} [sn−2​​fn−1​​fn−2​​]>> [ s n − 1 f n f n − 1 ] \begin{bmatrix}s_{n-1} & f_{n} & f_{n-1}\end{bmatrix} [sn−1​​fn​​fn−1​​]，可得到转移矩阵为
[ 1 0 0 1 1 1 0 1 0 ] \begin{bmatrix}1 & 0 & 0\\1 & 1 & 1\\0 & 1 & 0\end{bmatrix} ⎣⎡​110​011​010​⎦⎤​

code:

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[10][10];
int ans[10][10];
int p=9973;
void multi()
{
	int c[10][10];
	for(int i=1; i<=3; i++)	
		for(int j=1; j<=3; j++)
			c[i][j]=0;
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++)	
			for(int k=1; k<=3; k++)	
				c[i][j]=(c[i][j]+ans[i][k]*a[k][j])%p;
	for(int i=1; i<=3; i++)	
		for(int j=1; j<=3; j++)
			ans[i][j]=c[i][j];
}
void multi1()
{
	int c[10][10];
	for(int i=1; i<=3; i++)	
		for(int j=1; j<=3; j++)
			c[i][j]=0;
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++)	
			for(int k=1; k<=3; k++)	
				c[i][j]=(c[i][j]+a[i][k]*a[k][j])%p;
	for(int i=1; i<=3; i++)	
		for(int j=1; j<=3; j++)
			a[i][j]=c[i][j];
}
void ksm(int k)
{
	ans[1][1]=ans[2][2]=ans[3][3]=1;
	while(k!=0)
	{
		if(k&1)
			multi();
		multi1();
		k>>=1;
	}
}
void multi2()
{
	int c[10][10];
	for(int i=1; i<=1; i++)	
		for(int j=1; j<=3; j++)
			c[i][j]=0;
	for(int i=1; i<=1; i++)
		for(int j=1; j<=3; j++)	
			for(int k=1; k<=3; k++)	
				c[i][j]=(c[i][j]+a[i][k]*ans[k][j])%p;
	for(int i=1; i<=1; i++)	
		for(int j=1; j<=3; j++)
			ans[i][j]=c[i][j];
}
int main()
{
	scanf("%d", &n);
	a[1][1]=a[2][1]=a[2][2]=a[3][2]=a[2][3]=1;
	ksm(n-1);
	a[1][1]=1, a[1][2]=1, a[1][3]=1;
	multi2();
	printf("%d", ans[1][1]);
	return 0;
}