顾亦倾

用户名：1530222421

访问量：6812

签　名：

等　　级
排　　名	7199
经　　验	1336
参赛次数	0
文章发表	8
年　　龄	0
在职情况	学生
学　　校	武汉工程大学
专　　业

　　自我简介：

TA的其他文章

DNA-题解(C语言代码)
浏览：474

IP判断-题解(C++代码)
浏览：219

K-进制数-题解(C语言代码)
浏览：318

你可能喜欢

蓝桥杯2014年第五届真题-斐波那契-题解(C++代码)

　　作者: 顾亦倾　　　　发表时间：2020-02-13 17:26:50 浏览：2916　|　评论：4　

原题链接：蓝桥杯2014年第五届真题-斐波那契

######在了解矩阵快速幂之前，我们先要知道快速幂。快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高，它的基本原理是二进制。

对于a^n ， n一定可以用二进制表示。
	如156（10）=10011100（2）
	求解a^156，原来要进行156-1=155次乘法运算，现在的差不多运算次数就是他 二进制的长度*二进制中1的个数=8*4=24次
![](/image_editor_upload/20200213040754_40951.jpg)
######快速幂模板（计算x^y，结果为a）
```c
long long fastpow(long long x,long long y)
{
	long long a=1;//a为结果
	while(y)
	{
		if(y&1) a=a*x;
		x=x*x;//一个中间转移量. y每右移一次, x 就多一个平方
		y=y>>1;
	}
	return a;
} 
```

#####矩阵快速幂：就是把多次矩阵乘法用快速幂的形式算出，一般常用于递推的优化。
	相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法运算什么的也遵循矩阵的运算法则。
	矩阵快速幂的难点主要是在关系矩阵的构造上，只要关系矩阵构造出来了，其他的就只是套模板运算而已。
#####矩阵
```c
struct node {
	int mat[15][15];//定义矩阵 
}x,y; 
```
#####矩阵乘法
```c
node mul(node x,node y){//矩阵乘法 
	node tmp;
	for(int i=0;i<len;i++){
		for(int j=0;j<len;j++){
			tmp.mat [i][j]=0;
			for(int k=0;k<len;k++){
				tmp.mat [i][j]+=(x.mat [i][k]*y.mat [k][j])%mod;
			}
			tmp.mat [i][j]=tmp.mat[i][j]%mod;
		}
	}
	return tmp;
} 
```
#####快速矩阵幂
```c
node matpow(node x,node y,int num){//矩阵快速幂 
	while(num){
		if(num&1){
			y=mul(y,x);
		}
		x=mul(x,x);
		num=num>>1;
	}
	return y;
} 
```
######下面是一些常见递推式
![](/image_editor_upload/20200213045119_45296.png)

#####S(n)=f(n+2)-1
#####原式=(f(n+2)-1)%f(m)%p
####本题实现参考代码
```cpp
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
 
LL llmul( LL a,LL b,LL mod ) {
	a%=mod;a+=mod;a%=mod;
	b%=mod;b+=mod;b%=mod;
	if ( a<b )	swap( a,b );
	LL ret=0;
	while ( b ) {
		if ( b&1 )ret=( ret+a )%mod;
		a=( a<<1 )%mod;
		b/=2;
	}
	return ret;
}
struct matrix {
    LL x[3][3];
    matrix() {memset( x,0,sizeof x );}
};
matrix mmul( matrix &A,matrix &B,LL mod ) {
    matrix ret;
    for ( int i=1; i<=2; i++ )
		for ( int j=1; j<=2; j++ )
			for ( int k=1; k<=2; k++ )
        	ret.x[i][j]=( ret.x[i][j]+llmul( A.x[i][k],B.x[k][j],mod ) )%mod;
    return ret;
}
matrix E,A;
LL fib( LL n,LL mod ) {
    matrix O=E,B=A;
    while ( n ) {
        if ( n&1 )O=mmul( O,B,mod );
        B=mmul( B,B,mod );
        n/=2;
    }
    return O.x[1][2];
}
LL solve( LL n,LL m,LL mod ) {//f(n)%f(m)%mod
    LL t=n/m;
    //(f(m-1)^t*f(n%m))%f(m)%mod;
    //f(i)^2%f(i-1)=(-1)^(i+1)
    LL p=t/2,q=t%2;
    //{f(m-1)^q*(-1)^(pm)*f(n%m)}%f(m)%mod
    LL fuhao=p*m%2==0?1:-1;
    if ( q==0 ) {
        LL ans=fib( n%m,mod )*fuhao;
        ans%=mod;
        ans+=mod;
        return ans%mod;
    }
    if ( n%m==0 )return 0;
    //f(m-1)*f(n%m)*fuhao%f(m)%mod
    //x%y%mod=(x-a*y)%mod
    //a=[x/y]
    LL x=(llmul(fib(n%m,mod),fib(m-1,mod),mod)*fuhao%mod+mod)%mod;
    LL y=fib(m,mod);
    LL a=fib(n%m-1,mod);
    if(n%m%2==0)	a--;
    if(fuhao<0)	a++;
    a=(a%mod+mod)%mod;
    return ((x-llmul(a,y,mod))%mod+mod)%mod;
}
 
int main ()
{
    A.x[1][2]=A.x[2][1]=A.x[2][2]=1;
    E.x[1][1]=E.x[2][2]=1;
    LL n,m,mod;
    cin>>n>>m>>mod;
    cout<<( solve( n+2,m,mod )-1+mod )%mod<<endl;//S(n)=f(n+2)-1
    return 0;
}
```

0.0分

14 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

KAC

。。。

2022-05-16 16:04:44

天威难测

我真的是。。。看不懂啊兄弟，退赛吧

2022-02-02 20:43:33

自行车轮子

看到你这思路，我突然想退赛了

2020-09-25 22:49:17

LINK

疫情下只有刷题了

2020-04-04 20:52:34

顾亦倾

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并（C语言代码）

Lucky Word （C++代码）

C语言训练-斐波纳契数列（C语言代码）

母牛的故事（C语言代码）

校门外的树（C语言代码）

蓝桥杯2014年第五届真题-斐波那契-题解(C++代码)

评论区

精彩推荐

C语言训练-数字母（C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

【出圈】（C语言代码）

【回文数(二)】（C语言代码）

哥德巴赫曾猜测（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

蚂蚁感冒（C语言代码）

顾亦倾

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并 （C语言代码）

Lucky Word （C++代码）

C语言训练-斐波纳契数列 （C语言代码）

母牛的故事 （C语言代码）

校门外的树 （C语言代码）

蓝桥杯2014年第五届真题-斐波那契-题解(C++代码)

评论区

精彩推荐

C语言训练-数字母 （C语言代码）

蓝桥杯历届试题-九宫重排 （C++代码）

【出圈】 （C语言代码）

【回文数(二)】 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

蚂蚁感冒 （C语言代码）

数据结构-有序线性表的有序合并（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

母牛的故事（C语言代码）

校门外的树（C语言代码）

　　评论区

C语言训练-数字母（C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

【出圈】（C语言代码）

【回文数(二)】（C语言代码）

哥德巴赫曾猜测（C语言代码）

蚂蚁感冒（C语言代码）