HDU6198 number number number（打表 矩阵快速幂）

题意就是找到用K个斐波那契数组不成的最小的数字是谁。
先打表找规律

可以发现递推规律：F[n]=4*(F[n-1]-F[n-2])+F[n-3]

如果直接递推打表1e9是打不出来的，这时候就用矩阵快速幂来做。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int N=2e5+5;
const int mod=998244353;
ll n;
struct matrix{
	ll x[3][3];
};
matrix multi(matrix a,matrix b)//矩阵相乘
{
	matrix temp;
	memset(temp.x,0,sizeof(temp.x));
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
			{
				temp.x[i][j]+=a.x[i][k]*b.x[k][j];
				temp.x[i][j]%=mod;//负数取模的问题,除法取模
			}
	return temp;
}
matrix quick_multi(matrix a,ll n)//矩阵快速幂
{
	matrix temp=a;
	n--;
	while(n){
		if(n&1)
			temp=multi(temp,a);
		a=multi(a,a);
		n>>=1;
	}
	return temp;
}
int main()
{
	while(cin>>n)
	{
		if(n==1)
		{
			printf("4\n");
			continue;
		}
		else if(n==2)
		{
			printf("12\n");
			continue;
		}
		else if(n==3)
		{
			printf("33\n");
			continue;
		}
		matrix A;
		matrix ans;
		memset(A.x,0,sizeof(A.x));
		memset(ans.x,0,sizeof(ans.x));
		A.x[0][0]=4;A.x[1][0]=-4;A.x[2][0]=1;
		A.x[0][1]=1;A.x[1][2]=1;A.x[2][2]=0;
		ans.x[0][0]=33,ans.x[0][1]=12,ans.x[0][2]=4;
		A=quick_multi(A,n-3);
		ans=multi(ans,A);
		printf("%lld\n",(ans.x[0][0]+mod)%mod);
	}
	return 0;
}