没见过这玩意，写个题解记下。
题目大意
周知斐波那契数列定义为：
\[\operatorname{fib}(n)=\left\{
\begin{aligned}
1 & & n\le 2 \\
\operatorname{fib}(n-1)+\operatorname{fib}(n-2) & & n>2
\end{aligned}
\right.
\]
然后定义（\(n\le 0\) 函数值为 \(0\)）
\[f(n)=\sum_{i=1}^n \operatorname{fib}(i)
\]
你需要求出：
\[\sum_{i=1}^{n}\operatorname{fib}(i)(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))
\]
数据范围 \(n\le 10^{18}\)，数据组数 \(T\le 2\times 10^5\)，模数 \(2\le p \le 10^9+7\)
\operatorname{fib}
题目解析
第一次见这种题目，记录一下。
从这张图我们可以得到
\[f(n)=\sum_{i=1}^n \operatorname{fib}(i)=\operatorname{fib}(n)\operatorname{fib}(n+1)
\]
然后就是化式子
\[\begin{aligned}
& \sum_{i=1}^{n}\operatorname{fib}(i)(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i)) \\
&\text{展开} f(x) \\
= & \sum_{i=1}^{n}\operatorname{fib}(i)(\operatorname{fib}(i-2)\operatorname{fib}(i-1)+\operatorname{fib}^2(i)+\operatorname{fib}(i))\\
&\text{乘开，提出}\sum \operatorname{fib}^2(i) \\
= & \sum_{i=1}^{n}(\operatorname{fib}(i)\operatorname{fib}(i-1)\operatorname{fib}(i-2)+\operatorname{fib}^3(i))+ \sum_{i=1}^n\operatorname{fib}^2(i))\\
&\text{左边带入} \operatorname{fib}(i-2)=\operatorname{fib}(i)-\operatorname{fib}(i-1)\text{，右边带入上述公式}\\
= & \sum_{i=1}^{n}(\operatorname{fib}(i)\operatorname{fib}(i-1)(\operatorname{fib}(i)-\operatorname{fib}(i-1))+\operatorname{fib}^3(i))+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\
& \text{乘开} \\
= & \sum_{i=1}^{n}(\operatorname{fib}^2(i)\operatorname{fib}(i-1)-\operatorname{fib}(i)\operatorname{fib}^2(i-1)+\operatorname{fib}^3(i))+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\
& \text{提取公因式} \operatorname{fib}^2(i) \\
= & \sum_{i=1}^{n}(\operatorname{fib}^2(i)(\operatorname{fib}(i-1)+\operatorname{fib}(i))-\operatorname{fib}(i)\operatorname{fib}^2(i-1))+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\
& \text{合并} \operatorname{fib}(i-1)+\operatorname{fib}(i)=\operatorname{fib}(i+1) \\
= & \sum_{i=1}^{n}(\operatorname{fib}^2(i)\operatorname{fib}(i+1)-\operatorname{fib}^2(i-1)\operatorname{fib}(i))+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\
& \text{裂项相消} \\
= & \operatorname{fib}^2(n)\operatorname{fib}(n+1)-\operatorname{fib}^2(0)\operatorname{fib}(1)+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\\\
& \text{通过} \operatorname{fib}(n)=\operatorname{fib}(n-1)+\operatorname{fib}(n-2) \text{逆推得到} \operatorname{fib}(0)=0 \text{并带入}\\
= & \operatorname{fib}^2(n)\operatorname{fib}(n+1)+ \operatorname{fib}(n)\operatorname{fib}(n+1)\\
\end{aligned}
\]
矩阵乘法一次就可以同时算出 \(\operatorname{fib}(n)\) 和 \(\operatorname{fib}(n+1)\)。
时间复杂度 \(O(T\log n)\)。
ll n,p;
struct Mat{
ll a11,a12,a21,a22;
Mat operator * (const Mat y) const {
return (Mat){(this->a11*y.a11+this->a12*y.a21)%p,
(this->a11*y.a12+this->a12*y.a22)%p,
(this->a21*y.a11+this->a22*y.a21)%p,
(this->a21*y.a12+this->a22*y.a22)%p};
}
}st,base;
Mat pow(Mat x,ll y){
Mat res,tmp=x; res.a11=res.a22=1; res.a12=res.a21=0;
while(y){ if(y&1) res=res*tmp; tmp=tmp*tmp; y>>=1; } return res;
}
void work(){
fin>>n>>p; if(n==1){ fin<<2%p<<'\n'; return; }
st.a11=1; st.a12=1; base.a12=1; base.a21=1; base.a22=1;
st=(st*pow(base,n-1));
fin<<(st.a11+1)*st.a11%p*st.a12%p<<'\n';
}
int main(){
int T; fin>>T; while(T--) work(); return 0;
}