[数学记录] T345384 高维立方体
题目传送门
现在我们定义一个函数（注意在 \(n<1\) 时这个函数的值是 \(0\)）：
\[f(n)=\sum_{i=1}^n\operatorname{fib}^2(i)
\]
需要求出：
\[\sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))
\]
对于所有数据，\(1\le T\le 2\times 10^5\)，\(1\le n\le 10^{18}\)，\(2\le p\le 10^9+7\)。
很有意思的题
先对 \(\rm fib^2(i)\) 进行化简，裂项一下得：
\[\begin{aligned}\text{fib}^2(i)&=\left(\text{fib}(i+1)-\text{fib}(i-1)\right)\text{fib}(i))\\&=\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1)\end{aligned}
\]
所以
\[f(n)=\sum_{i=1}^n{\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1)=\text{fib}(n+1)\text{fib}(n)}
\]
将 \(f(i-2)\) 代入原式得：
\[\begin{aligned}&\text{fib}(i)\left(\text{fib}(i-1)\text{fib}(i-2)+\text{fib}^2(i)+\text{fib}(i)\right)\\=\:&\text{fib}(i)(\text{fib}(i-1)\text{fib}(i-2)+\text{fib}(i+1)\text{fib}(i)-\text{fib}(i)\text{fib}(i-1))+\text{fib}^2(i)\\=\:&\text{fib}(i)[\:\:\text{fib}(i+1)\text{fib}(i)-\text{fib}(i-1)(\:\text{fib}(i)-\text{fib}(i-2)\:)\:\:]+\text{fib}^2(i)\\=\:&\text{fib}(i+1)\text{fib}^2(i)-\text{fib}^2(i)\text{fib}(i-1)+\text{fib}^2(i)\end{aligned}
\]
求和得：
\[\text{fib}(n+1)\text{fib}^2(n)+\text{fib}(n+1)\text{fib}(n)
\]
矩阵快速幂优化即可，注意卡常
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M=2;
int T;
LL n,p;
struct matrix
{
int row,col;
LL data[M][M];
matrix(int r,int c)
{
row=r;
col=c;
memset(data,0,sizeof(data));
}
};
matrix a(2,2);
matrix ans(1,2);
matrix operator * (const matrix &x,const matrix &y)
{
matrix c(x.row,y.col);
for(int i=0; i<x.row; i++)
{
for(int j=0; j<y.col; j++)
{
for(int k=0; k<x.col; k++)
c.data[i][j]+=x.data[i][k]*y.data[k][j];
c.data[i][j]%=p;
}
}
return c;
}
void init()
{
a.data[0][1]=a.data[1][0]=a.data[1][1]=ans.data[0][1]=1;
a.data[0][0]=ans.data[0][0]=0;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&p);
init();
for(; n; n>>=1)
{
if(n&1)
ans=ans*a;
a=a*a;
}
LL s=(ans.data[0][1]*ans.data[0][0]%p*ans.data[0][0]%p+ans.data[0][1]*ans.data[0][0]%p)%p;
printf("%lld\n",s);
}
return 0;
}