斐波那契数列III

Description

求数列f[n]=f[n-1]+f[n-2]+1的第N项.f[1]=1,f[2]=1.

Input

n(1＜n＜２^31-1)

Output

第Ｎ项的结果 mod 9973

Sample Input

12345
Sample Output

8932

解题思路



代码

#include<cstdio>
using namespace std;
long long n,k;
struct node
{
   
	long long n,m;
	long long oo[5][5];
}a,b,c;
node operator*(node x,node y)
{
   
	node z;
	for(long long i=1;i<=x.n;i++)
	 for(long long j=1;j<=y.n;j++)
	  z.oo[i][j]=0;
	for(long long o=1;o<=x.m;o++)  
	 for(long long i=1;i<=x.n;i++)
	  for(long long j=1;j<=y.n;j++)
	   z.oo[i][j]=(z.oo[i][j]+x.oo[i][o]*y.oo[o][j])%9973;
	return z;
}
void ksm(long long k)
{
   
	if (k==1)
	{
   
		c=a;
		return;
	}
	ksm(k/2);
	c=c*c;
	if (k&1) c=c*a;
}
int main()
{
   
	scanf("%lld",&n);
	a.n=a.m=3;
	a.oo[1][2]=a.oo[2][1]=a.oo[2][2]=a.oo[3][2]=a.oo[3][3]=1;
	ksm(n-1);
	b.n=1;
	b.m=3;
	b.oo[1][1]=b.oo[1][2]=b.oo[1][3]=1;
	b=b*c;
	printf("%lld",b.oo[1][1]);
	return 0;
}

谢谢