写在前面的注意事项,注!本题主要使用动态规划算法 不是标准答案,经过测试,主要只能实现50%的数据,
还望各位题友给出更好的方法
题目描述
斐波那契数列大家都非常熟悉。它的定义是:
f(x) = 1 .... (x=1,2)
f(x) = f(x-1) + f(x-2) .... (x>2)
对于给定的整数 n 和 m,我们希望求出:
f(1) + f(2) + … + f(n) 的值。但这个值可能非常大,所以我们把它对 f(m) 取模。
公式如下:
示例
但这个数字依然很大,所以需要再对 p 求模。
输入描述:
输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
样例
例如:
样例输入:
2 3 5
输出描述
输出为 1 个整数
例如:
对应输出:
0
运行限制
最大运行时间:1s
最大运行内存: 256M
JAVA 代码
import java.math.BigInteger;
import java.util.Scanner;
public class _斐波那契 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int p = sc.nextInt();
BigInteger fb_res = new BigInteger("0");
BigInteger m_res = new BigInteger(m+"");
BigInteger tmp = new BigInteger("0");
BigInteger P = new BigInteger(p+"");
for (int i = 1; i <= n; i++) {
tmp = fbn(i);
fb_res = fb_res.add(tmp);
}
m_res = fbn(m);
BigInteger res = fb_res.mod(m_res).mod(P);
System.out.println(res);
}
public static BigInteger fbn(int n) {
BigInteger one = new BigInteger("1");
BigInteger zero = new BigInteger("0");
BigInteger[] dp = new BigInteger[(n + 1)];
dp[0] = zero;
dp[1] = one;
for (int i = 2; i < n + 1; i++) {
dp[i] = dp[i - 1].add(dp[i - 2]);
}
return dp[n];
}
}
中文名是真的顶
用矩阵快速幂算斐波那契感觉可以,但是fm不知道怎么处理,另外Sn其实就等于F(n+2) - 1的