佳佳的 Fibonacci 题解
题目：
题解：
数据范围很大，暴力超时，考虑的是矩阵优化递推，关键是求出递推矩阵，然后结合矩阵快速幂求解
如何求解递推矩阵？
我们首先知道斐波那契的递推式：
f[i]=f[i-1]+f[i-2]——>①
然后题目中给我们了T(n)的递推式：
T(n)=F[1]+2F[2]+3F[3]+...+nF[n]——>②
考虑从T(n)推得T(n+1)
T(n+1)=T(n)+(n+1)*F[n+1]
由①的：
T(n+1)=T(n)+(n+1)*(F[n]+F[n-1])=T(n)+n*F[n]+n*F[n-1]+F[n]+F[n-1])
我选择T[n-1],nF[n],nF[n-1],F[n],F[n-1]作为行向量
从而推出T[n],(n+1)F[n+1],(n+1)F[n],F[n+1],F[n];
我们现在需要找出底数矩阵A,它的规模应该是5*5的（显然
下面请填表：
| T(n-1) | nF[n] | nF[n-1] | F[n] | F[n-1] | |
|---|---|---|---|---|---|
| T(n+1) | |||||
| (n+1)F[n+1] | |||||
| (n+1)F[n] | |||||
| F[n+1] | |||||
| F[n] |
填完应该长这样：
| T(n-1) | nF[n] | nF[n-1] | F[n] | F[n-1] | |
|---|---|---|---|---|---|
| T(n+1) | 1 | 1 | 0 | 0 | 0 |
| (n+1)F[n+1] | 0 | 1 | 1 | 1 | 1 |
| (n+1)F[n] | 0 | 1 | 0 | 1 | 0 |
| F[n+1] | 0 | 0 | 0 | 1 | 1 |
| F[n] | 0 | 0 | 0 | 1 | 0 |
转置一下，就得到了矩阵A:
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
然后可以得出：
{T(n) (n+1)F[n+1] (n+1)F[n] F[n+1] F[n]
=A^(n-1) * {T(2) 2F[2] 2F[1] F[2] F[1]}
这就是初始矩阵：
{3 3 3 1 1}
代码实现也很容易，注意A要转置（矩阵乘行向量）了解更多
给出代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
int n,mod;
il int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
il void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
struct mat{
int m[10][10];
mat(){
memset(m,0,sizeof(m));
}
};
mat operator*(const mat& a,const mat& b){
mat c;
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
for(int k=1;k<=5;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return c;
}
il mat fast_pow(int b){
mat a,zero;
a.m[1][1]=1;
a.m[2][1]=1;
a.m[3][1]=1;
a.m[2][2]=1;
a.m[3][2]=1;
a.m[4][2]=1;
a.m[5][2]=1;
a.m[2][3]=1;
a.m[4][3]=1;
a.m[4][4]=1;
a.m[5][4]=1;
a.m[4][5]=1;
zero.m[1][1]=3;
zero.m[1][2]=3;
zero.m[1][3]=3;
zero.m[1][4]=1;
zero.m[1][5]=1;
while(b){
if(b&1) zero=zero*a;
b>>=1;
a=a*a;
// for(int i=1;i<=5;i++){
// for(int j=1;j<=5;j++){
// cerr<<zero.m[i][j]<<" ";
// }
// cerr<<endl;
// }
}
return zero;
}
main(void){
n=read(),mod=read();
if(n==1){
cout<<1<<endl;
return 0;
}
mat ans=fast_pow(n-2);
write(ans.m[1][1]%mod);
}