题意&思路
代码
/*
题意简化:
用 T(n)=(F1+2F2+3F3+…+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。
解题方法:
算法一:矩阵乘法
*/
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=4;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
int n,m;
void mul(int c[][N],int a[][N],int b[][N]){
static int t[N][N];
memset(t,0,sizeof t);
for(int i=0;i<N;i++)
for(int k=0;k<N;k++)
for(int j=0;j<N;j++)
t[i][j]=(t[i][j]+(ll)a[i][k]*b[k][j])%m;
memcpy(c,t,sizeof t);
}
int main(){
cin>>n>>m;
int f1[N][N]={1,1,1,0};
int a[N][N]={
{0,1,0,0},
{1,1,1,0},
{0,0,1,1},
{0,0,0,1},
};
int k=n-1;
while(k){
if(k&1)mul(f1,f1,a);
mul(a,a,a);
k>>=1;
}
cout<<(((ll)n*f1[0][2]-f1[0][3])%m+m)%m<<endl;
return 0;
}