【算法】小强爱数学（迭代公式）

本文主要是介绍【算法】小强爱数学（迭代公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 问题
- 输入
- 输出
- 示例
- 分析
- 思路
- 代码

问题

小强发现当已知 $x y = B$ 以及 $x + y = A$ 时,能很轻易的算出 $x_ {n}$ + $y_ {n}$ 的值.但小强想请你在已知A和B的情况下,计算出 $x + y$ 的值.因为这个结果可能很大所以所有的运算都在模1e9+7下进行.

输入

第一行输入一个正整数T.表示有T组数据
接下来T行, 每行输入三个整数A,B和n
$1<=T<=100\\ 0<=A,B<=1e9+7\\ 1<=n<=1e5$

输出

输出 $T$ 行,每一行表示每组数据的结果.

示例

输入例子：
3
4 4 3
2 3 4
5 2 6
输出例子：
16
999999993
9009

分析

本题实际上就是个数学问题，积累了递推公式雀氏很好做，否则就很操蛋

递推公式
$$
\begin{aligned}

nihao
\end{aligned}
$$

$KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ &\ 已知 A = x + …$

证明
$KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ R_{n} &\ = (x …$

思路

迭代计算，类似斐波那契

代码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static final int mod = 1000000000 + 7;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt(), n;long A, B; for (int i = 0; i < T; ++i) {A = sc.nextInt(); B = sc.nextInt(); n = sc.nextInt();long[] dp = new long[n + 1];dp[1] = A % mod; dp[2] = (A * A % mod - 2 * B % mod + mod) % mod;if (n == 1) {System.out.println(dp[1]);}else if (n == 2) {System.out.println(dp[2]);}else {for (int j = 3; j <= n; ++j) {dp[j] = (A * dp[j - 1] % mod - B * dp[j - 2] % mod + mod) % mod;}System.out.println(dp[n]);}}}
}