hdu6198 17沈阳网络赛矩阵快速幂_沈阳矩阵快速幂-CSDN博客

本文链接：https://blog.csdn.net/animalcoder/article/details/77940493

题意：给出N，问最小的不能成为N个斐波那契数列之和的数是哪个（N个斐波那契数列任选一项，并相加）

PS：一开始还以为是FFT= = 然后枚举前两个就找到思路了

斐波那契数列： 1 2 3 5 8 13 21 34 55 89
比如：N=1：ans=4，因为4是最小的不能成为1个斐波那契数列的数
N=2：ans=12,因为11=8+3 10=5+5 9=8+1......
N=3：这时候就想到只要选一个，剩下两个数最小不能组成12，所以只要找前后项相差大于12的，

21 34 之间相差13 所以ans=21+12=33;

N=4：找前后项相差33的 55 89满足，ans=55+33=88;
规律已经很明显了，输出 2N*2项的斐波那契-1即可

矩阵快速幂秒解，AC代码如下：

/*模板描述 
//原题hdu4549 矩阵快速幂 这题幂在指数b上所以快速幂的mod要跟着改
//a^b%p =( a(mod)p^ bmod欧拉p )modp
//矩阵快速幂，fi=fi-1+ 5fi-2 + fi-3- fi-4
//MOD是取模
//maxn是数组大小
//unit是单位矩阵 init_unit()是初始化单位矩阵
// 重载了*
//有矩阵快速幂函数和输出函数*/ 
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
const int maxn = 2;//看着办
int MOD  = 998244353;
#define mod(x) ((x)%MOD)
#define ll long long
struct mat
{
	ll m[maxn][maxn];
};
mat unit;//单位矩阵
// 重载*使之能进行矩阵乘法运算
mat operator * (mat a,mat b)
{
	mat ret;
	ll x;
	for(int i=0; i<maxn; i++)
	{
		for(int j=0; j<maxn; j++)
		{
			x = 0;
			for(int k=0; k<maxn; k++)
				x += ((ll)a.m[i][k]*b.m[k][j])%(MOD);//MOD可能会改 此处可换快速乘加速= =
			ret.m[i][j] = x%(MOD);//MOD可能会改 = =
		}
	}
	return ret;
}
void op(mat &a)//输出矩阵，自己调输出范围
{
	for(int i=0; i<maxn; i++)
	{
		for(int j=0; j<maxn; j++)
			cout<<a.m[i][j]<<" ";
		cout<<endl;
	}
}
// 初始化单位矩阵unit
void init_unit()
{
	for(int i=0; i<maxn; i++)
		for(int j=0; j<maxn; j++)
			unit.m[i][j]=0;
	for(int i=0; i<maxn; i++)
		unit.m[i][i] = 1;
}
//初始化几把 
void init_mat(mat &mmm)
{
	for(int i=0; i<maxn; i++)
		for(int j=0; j<maxn; j++)
			mmm.m[i][j]=0;
}
// // 计算矩阵a的x次幂 与普通快速幂原理相同 
mat pow_mat(mat a,ll x)
{
	mat ret = unit;
	while(x)
	{
		if(x&1) ret = ret*a;
		a = a*a;
		x >>= 1;
	}
	return ret;
}
ll mod_pow(ll x,ll n,ll mod)//快速幂 余数
{
	ll res=1;
	while(n>0)
	{
		if(n&1)//n的二进制最右位是1，即奇数
			res=res*x%mod;
		x=x*x%mod;
		n=n>>1;		 //相当于n/=2;
	}
	return res;
}
int main()
{
	ll n1;
	ll k;
	mat m1;//左矩阵
	mat m2;//右矩阵
	init_unit();
	init_mat(m1);
	init_mat(m2);
	//不同题目不同构造。。
	init_mat(m2);
	m2.m[0][0]=1;
	m2.m[1][0]=0;
	m1.m[0][0]=1;
	m1.m[0][1]=1;
	m1.m[1][0]=1;
	m1.m[1][1]=0;

	//op(m1);
	while(~scanf("%I64d",&k))
	{
		mat mt;//暂时矩阵
		init_mat(mt);
		mt=pow_mat(m1,2*k+2);
		mt=mt*m2;
		printf("%I64d\n",mt.m[0][0]-1);
	}
	return 0;
}