做网站是用的那个开发软件,搜索引擎网站入口,word 发布wordpress,中山企业网站建设方案问题描述 斐波那契数列大家都非常熟悉。它的定义是#xff1a;
f(x) 1 …. (x1,2) f(x) f(x-1) f(x-2) …. (x2)
对于给定的整数 n 和 m#xff0c;我们希望求出#xff1a; f(1) f(2) … f(n) 的值。但这个值可能非常大#xff0c;所以我们把它对 f(m) 取模…问题描述 斐波那契数列大家都非常熟悉。它的定义是
f(x) 1 …. (x1,2) f(x) f(x-1) f(x-2) …. (x2)
对于给定的整数 n 和 m我们希望求出 f(1) f(2) … f(n) 的值。但这个值可能非常大所以我们把它对 f(m) 取模。 公式如下 但这个数字依然很大所以需要再对 p 求模。 输入格式 输入为一行用空格分开的整数 n m p (0 n, m, p 10^18) 输出格式 输出为1个整数表示答案 样例输入 2 3 5 样例输出 0 样例输入 15 11 29 样例输出 25 解析数据量超大需要用到大数处理在求解斐波那契数列的时候要用矩阵快速幂的方法下面的代码只能的40分具体原因是在求f(1) f(2) … f(n)的时候没有处理好做循环的时候不能用long n做上界的确可以改成大数进行循环但是这又牵扯到大数进行位运算这里不是很明白所以也无法给出满分的代码。
import java.math.BigInteger;
import java.util.Scanner;public class Main {public static BigInteger[][] ZERO {{BigInteger.ZERO,BigInteger.ZERO}, {BigInteger.ZERO,BigInteger.ZERO}};public static BigInteger[][] KEY {{BigInteger.ONE,BigInteger.ONE}, {BigInteger.ONE,BigInteger.ZERO}};public static BigInteger MOD;public static BigInteger[][] mergeMulti(long n) {if(n 0) {return ZERO;}if(n 1) {return KEY;}if((n1) 0) { // n为偶数BigInteger[][] temp mergeMulti(n1);return matrixMulti(temp, temp);} else { // n为奇数BigInteger[][] temp mergeMulti(n1);return matrixMulti(matrixMulti(temp, temp), KEY);}}public static BigInteger[][] matrixMulti(BigInteger[][] A, BigInteger[][] B) {BigInteger[][] result new BigInteger[A.length][B[0].length];for(int i 0;i A.length;i) {for(int j 0;j B[0].length;j) {result[i][j] BigInteger.ZERO;for(int k 0;k A[0].length;k) {result[i][j] result[i][j].add(A[i][k].multiply(B[k][j]));}}} return result;}public static BigInteger sum(long n) {BigInteger cnt BigInteger.ZERO;for (int i 1; i n; i) {cnt cnt.add(mergeMulti(i)[0][1]);}return cnt;}public static void main(String[] args) {Scanner in new Scanner(System.in);long n in.nextLong();long m in.nextLong();MOD in.nextBigInteger();BigInteger result sum(n);result result.mod(mergeMulti(m)[0][1]).mod(MOD);System.out.println(result);}
}
