(a + b) mod n = a mod n + b mod n
(a * b) mod n = a mod n * b mod n
也就是说f(x)只进行+-*运算的时候, 最后f(x) mod n, 可以把mod n加入到f(x)的每一项中
滚动数组
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
const int MOD = 1e4;
int p, q, k;
int a[N];
int main()
{
cin >> a[0] >> a[1] >> p >> q >> k;
for (int i = 2; i <= k; i ++)
a[i] = (p * a[i - 1] + q * a[i - 2]) % MOD;
cout << a[k] % MOD << endl; // 注意k = 1的情况
return 0;
}
用 DFS递归 会报 TLE
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 1e4;
int a0, a1, p, q, k;
int dfs(int n)
{
if (n == 0) return a0;
if (n == 1) return a1;
return (p * dfs(n - 1) + q * dfs(n - 2)) % MOD;
}
int main()
{
cin >> a0 >> a1 >> p >> q >> k;
cout << dfs(k) << endl;
return 0;
}