蓝桥杯 新型斐波那契数列

问题描述

新型斐波那契数列的第一、二、三项都为1，从第四项起每一项等于前面三项之和，求此数列第n项模m的余数。

输入格式

输入一行为两个整数n、m，用空格隔开。

输出格式

输出一行为新型斐波那契数列第n项模m的余数。

样例输入

7 3

样例输出

2

数据规模和约定

1≤n≤10^18，1≤m≤100

解题思路

对于求解斐波拉契数列的第N项，通常有三种常用的方法：递归、数组、矩阵。

因为本题的数据规模是$10^{18}$，前两种方法直接计算方法必定会超时，这里着重介绍一下矩阵解法，可以将时间复杂度降低为$O(lg(n))$

定义$F_i$是新型斐波拉契数列的第i项，对于新型斐波拉契数列的前四项，能够得到：
$$\left(\begin{array}{c}{F}_2\\ F_3\\ F_4\end{array}\right)=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right)\left(\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right)$$
同样有：
$$\left(\begin{array}{c}{F}_3\\ F_4\\ F_5\end{array}\right)=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right)\left(\begin{array}{c}{F}_2\\ F_3\\ F_4\end{array}\right)={\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right)}^2\left(\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right)$$
以此能够推出一般式：
$$\left(\begin{array}{c}{F}_{n-2}\\ F_{n-1}\\ F_n\end{array}\right)={\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right)}^{n-3}\left(\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right)$$
而矩阵的幂次方乘法能够使用快速幂计算，能够将时间复杂度缩短为$O(lgN)$，即可解决问题。

代码

import java.io.*;
import java.util.*;public class Main {public static class matrix {public long[][] values;matrix(){values = new long[3][3];}matrix(matrix clone){this.values = clone.values.clone();}public static matrix init(){matrix matrix = new matrix();matrix.values[0][1] = 1;matrix.values[1][2] = 1;Arrays.fill(matrix.values[2], 1);return matrix;}}// 矩阵乘法public static matrix mutiply(matrix mt1, matrix mt2){matrix temp = new matrix();for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {for (int k = 0; k < 3; ++k) {temp.values[i][j] += (mt1.values[i][k] * mt2.values[k][j]) % m;temp.values[i][j] %= m;}}}return temp;}static int m;// 矩阵幂public static matrix pow(matrix mt, long val) {--val;matrix temp = mt;while (val != 0) {if ((val & 1) == 1) {mt = mutiply(mt, temp);}val >>= 1;temp = mutiply(temp, temp);}return mt;}public static void main(String[] args) throws FileNotFoundException {Scanner cin = new Scanner(System.in);long n =  cin.nextLong();m = cin.nextInt();if (m == 1) {System.out.println(0);return;}matrix init = matrix.init();init = pow(init, n - 3);System.out.println((init.values[2][0] + init.values[2][1] + init.values[2][2]) % m);}
}