题目描述

佳佳对数学，尤其对数列十分感兴趣。

在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。

例如用 $S(n)$ 表示 Fibonacci 前 n 项和 modm 的值，即 $S(n)=(F1+F2+…+Fn) \pmod m$，其中 $F1=F2=1,Fi=Fi−1+Fi−2$。

可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。

用 $T(n)=(F1+2F2+3F3+…+nFn) \pmod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $mod$ $m$ 的值。

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

输入格式
共一行，包含两个整数 $n$ 和 $m$。

输出格式
共一行，输出 $T(n)$ 的值。

数据范围
$1≤n,m≤2^{31}−1$

样例

输入样例：
5 5
输出样例：
1
样例解释
T(5)=(1+2×1+3×2+4×3+5×5)mod5=1

算法

(矩阵快速幂)

这道题让求的$T(n) = (F_{1} + 2 * F_{2} + 3 * F_{3} + .... + n * F_{n})$,我们将这个公式化简得到$T_{n} = s_{n} + (s_{n} - s_{1}) + (s_{n} - s_{2}) + … + (s_{n} - s_{n-1})$,继续推导得$T_{n} = n * s_{n} - (s_{1} + s_{2} + … + s_{n-1})$,变形得到$T_{n} = (n + 1) * s_{n} - (s_{1} + s_{2} + … + s_{n-1} + s_{n})$,从最后这个式子可以发现，如果想要求出$T_{n}$，需要维护两个条件一个是斐波那契数列前$n$项的和$s_{n}$，另一个是$s_{n}$的前$n$项和$p_{n}$,所以这里我们设$F_{n} = {f_{n}, f_{n+1}, s_{n}, p_{n}\}$,然后我们考虑$F_{n+1} = f_{n+1}, f_{n+2}, s_{n+1}, p_{n+1}$可以通过$F_{n}$乘一个什么矩阵得到呢？这里的答案为：

0 1 0 0
1 1 1 1
0 0 1 1
0 0 0 1

有了这个矩阵$A$之后，$F_{n}$的值就为$F_{1} * A^{n-1}$,最终$T_{n}$的值就可以通过上面的式子计算出来了。

时间复杂度

这道题的时间复杂度为$O(log_{2}^{n} \* 4 ^ 3)$

java 代码

import java.io.*;

class Main{
    static int N = 4, MOD;

    static void mul(int[] a, int[][] b){
        int[] temp = new int[N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                temp[i] = (int)((temp[i] + (long)a[j] * b[j][i] % MOD) % MOD);
            }
        }

        for(int i=0; i<N; i++) a[i] = temp[i];
    }

    static void mul(int[][] a, int[][] b){
        int[][] temp = new int[N][N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    temp[i][j] = (int)((temp[i][j] + (long)a[i][k] * b[k][j] % MOD) % MOD);
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                a[i][j] = temp[i][j];
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = in.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        MOD = Integer.parseInt(arr[1]);

        int[] F1 = {1, 1, 1, 1};

        int[][] A = {
            {0, 1, 0, 0},
            {1, 1, 1, 1},
            {0, 0, 1, 1},
            {0, 0, 0, 1}
        };

        int an = n;
        n --;
        while(n != 0){
            if(n % 2 != 0) mul(F1, A);
            mul(A, A);
            n /= 2;
        }

        int res = (int)((((long)F1[2] * (an + 1) - F1[3]) % MOD + MOD) % MOD);
        System.out.println(res);
    }
}