this

40分 WA

题面概括

Fi为斐波那契第i项 求T(n)=F1*1+F2 *2+...+ Fn * n

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll q,mod;
struct node
{
	ll n,m,x[10][10];
}A,B,ans;
node ji(node u,node o)
{
	node res;
	memset(res.x,0,sizeof(res.x));
	for(int i=1;i<=u.n;i++)
	{
		for(int j=1;j<=o.m;j++)
		{
			for(int l=1;l<=u.m;l++)
			{
				res.x[i][j]=(res.x[i][j]+(u.x[i][l]*o.x[l][j])%mod)%mod;
			}
		}
	}
	res.n=u.n;
	res.m=o.m;
	return res;
}
node p(node num,ll go){
	node res;
	memset(res.x,0,sizeof(res.x));
	res.n=res.m=4;
	res.x[1][1]=1;
	res.x[2][2]=1;
	res.x[3][3]=1;
	res.x[4][4]=1;
	if(!go){
		return res;
	}
	res=p(num,go>>1);
	if(go&1){
		return ji(ji(res,res),num);
	}
	return ji(res,res);
}
int main()
{
	cin>>q>>mod;
	A.x[1][2]=1;
	B.x[1][2]=B.x[2][3]=B.x[2][4]=B.x[2][1]=B.x[2][2]=B.x[3][3]=B.x[3][4]=B.x[4][4]=1;
	q--;
	A.n=A.m=B.n=B.m=4;
	ans=ji(A,p(B,q));
	cout<<((ans.x[1][2]*(q+1))%mod-ans.x[1][4]+mod)%mod;
}