题目链接
题目描述
私货：《消失点》——洛天依\Icelter。
做题思路
1.我推它的公式
双倍题解给下一位
首先，\(f_i=f_{i-1}+f_{i-2}\)
其次，\(T_i=T_{i-1}+if_i\)
易得，\(T_i=T_{i-1}+nf_{n-1}+nf_{n-2}\)
所以我们考虑如何使用base来转换出\(T_i\)
2.我搞它的矩阵
我们的base一定包含那么五个元素，分别是：
\(T_{i-1}\)、\(nf_{i-1}\)、\(nf_{i-2}\)、\(f_i-1\)、\(f_{i-2}\)
那么我们先列出一个表格，表格的第一行是这五个元素，第一列是a*base后得到的元素。
表格里的1表示相加
| \(T_n-1\) | \(nf_{n-1}\) | \(nf_{n-2}\) | \(f_{n-1}\) | \(f_{n-2}\) | |
|---|---|---|---|---|---|
| \(T_i\) | 1 | 1 | 1 | ||
| \(n+1f_n\) | 1 | 1 | 1 | 1 | |
| \(n+1f_{n-1}\) | 1 | 1 | |||
| \(f_{n}\) | 1 | 1 | |||
| \(f_{n-1}\) | 1 |
根据矩阵乘法中的一些东西：
关于矩阵乘中的矩阵乘行向量或列向量
我们可以知道，首先5*5的矩阵相乘，要使左矩阵的行向量乘右矩阵的列向量得到第一个元素\(T_i\)
那么就要让上述表格的第一行作为行向量是乘号左边的矩阵，倒置表格使表格的数是：
1 0 0 0 0
1 1 1 0 0
1 1 0 0 0
0 1 1 1 1
0 1 0 1 0
作为乘号右边的矩阵。
或者说我们让上述表格的第一行是列向量作为乘号右边的矩阵，不倒表格作为乘号左边的矩阵。
我们以第一种做法为例
再来推初始矩阵n=3很好推叭
3 3 3 1 1
代码实现
Miku's Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=2147483647;
typedef long long intx;
int n,m;
intx ans;
struct matrix{
intx num[8][8];
matrix clear(){memset(num,0,sizeof(num));}
};matrix a,base;
matrix operator*(matrix &x,matrix &y){
matrix res;
res.clear();
for(int k=1;k<=5;++k){
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
res.num[i][j]=(res.num[i][j]+x.num[i][k]*y.num[k][j]%m)%m;
}
}
}
return res;
}
void pre(){
base.clear();
base.num[1][1]=1;
base.num[2][1]=base.num[2][2]=base.num[2][3]=1;
base.num[3][1]=base.num[3][2]=1;
base.num[4][2]=base.num[4][3]=base.num[4][4]=base.num[4][5]=1;
base.num[5][2]=base.num[5][4]=1;
a.num[1][1]=a.num[1][2]=a.num[1][3]=3;
a.num[1][4]=a.num[1][5]=1;
}
void get(int k){
while(k){
if(k&1) a=a*base;
k=k>>1;
base=base*base;
}
}
void input(){
scanf("%d%d",&n,&m);
}
int main(){
input();
pre();
if(n==1){
printf("1");
return 0;
}
if(n==2){
printf("3");
return 0;
}
n-=2;
get(n);
intx ans=a.num[1][1]%m;
printf("%lld\n",ans);
return 0;
}