「一本通 6.5 例 4」佳佳的 Fibonacci

题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用 S(n) 表示 Fibonacci 前 n 项和 mod m 的值，即 S(n)=(F1+F2+…+Fn) mod m，其中 F1=F2=1, Fi=Fi-1+Fi-2。可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。用 T(n)=(F1+2F2+3F3+…+nFn) mod m 表示 Fibonacci 数列前 n 项变形后的和 mod m 的值。

现在佳佳告诉你了一个 n 和 m，请求出 T(n) 的值。

输入输出格式

输入格式：

输入数据包括一行，两个用空格隔开的整数 n,m。

输出格式：

仅一行，T(n) 的值。

题目分析：

已知

则

整理可得

因此

然后就是常规矩阵乘法操作：

#include#define ll long longusing namespace std;ll n,p;struct N{ll a[3][3];}A,A_1;inline N cheng(N x,N y){N z;memset(z.a,0,sizeof(z.a));for(ll i=1;i<=2;i++) for(ll j=1;j<=2;j++) for(ll k=1;k>n>>p;A.a[1][1]=1,A.a[1][2]=1,A.a[2][1]=1,A.a[2][2]=0;ll S=n*ksm(n+2).a[1][2]-ksm(n+3).a[1][2]+2;cout<<(S+p)%p;return 0;}