『STA - R3』高维立方体 - Luogu - 题目详情

ID: 8759

远端评测题

1500ms

256MiB

难度: 6

上传者:

标签>

数学

O2优化

矩阵加速

斐波那契,Fibonacci

题目描述

如下定义斐波那契数列：

\operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases}

现在我们定义一个函数（注意在 $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))

的值，答案对输入的 $p$ 取模。

注： $\operatorname{fib}^2(x)$ 表示 $\operatorname{fib}(x)$ 的平方。

本题有多组数据。

第一行一个整数 $T$ ，表示数据的组数。

对于每组数据，一行两个整数 $n,p$ 。

对于每组数据，输出一行一个整数，表示答案对 $p$ 取模后的结果。

4
18
60

样例解释：

对于第一组数据， $1\times(0+1^2+1)+1\times(0+1^2+1)=4$ 。

对于第二组数据， $1\times(0+1^2+1)+1\times(0+1^2+1)+2\times(1+2^2+2)=18$ 。

本题采用捆绑测试。

对于所有数据， $1\le T\le 2\times 10^5$ ， $1\le n\le 10^{18}$ ， $2\le p\le 10^9+7$ 。