I encountered the following problem, but I don't know how to solve it.
First of all, there's this kind of ignition.
f(n) = 3f(n-1) + f(n-2) - f(n-3), f(0) = 0, f(1) = 1, f(2) = 2
And the problem is just to print out the f(n) value for a given n(100 million;;
It's natural to solve it by adding it linearly, but if you put 100 million in college, you'll have a timeout, so I thought about another direction, but I can't think of it.
There are two things that I think big about.
1) To extract another equation by mathematically transforming the ignition equation.
2) Convert it to a sub-ignition formula and make it an expression for f(2), f(1), and f(0). However, in this case, the coefficient will come out as the sum of exponential equations of 3, but I didn't go deep because I thought there would be a difference in the amount of computation.
But neither of them seems to lead to an answer. I would appreciate it if you could give me some advice on how to reduce the amount of computation. Below is a code that I solved linearly, but it may not be accurate because it was restored to memory. I'd appreciate your understanding.
int solution(int n) { if (n == 1) return 1; if (n == 2) return 2;
unsigned fm3;
unsigned fm2 = 0;
unsigned fm1 = 1;
unsigned f = 2;
int ans;
for (int i = 3; i <= n; i++) {
fm3 = fm2;
fm2 = fm1;
fm1 = f;
f = (3 * fm1)%= 100000007 + fm2 - fm3;
ans = f % 100000007;
if (fm2 >= 100000007 && fm1 >= 100000007 && f >= 100000007) {
fm2 %= 100000007;
fm1 %= 100000007;
f %= 100000007;
}
}
return ans;
}
c++
#include <cstdio>
int solve(int);
int main(void)
{
int n;
scanf("%d", &n); // Integer greater than or equal to 0
printf("%d\n", solve(n));
return 0;
}
int solve(int n)
{
if (n <= 2)
return n;
int idx = 0;
long f[4] = {0, 2, 1, 0}; //f[idx] = f(n) // f[(idx + 1) % 4] = f(n-1) // f[(idx + 2) % 4] = f(n-2) // f[(idx + 3) % 4] = f(n-3)
for (int i = 3; i <= n; i++)
{
f[idx] = (3 * f[(idx + 1) % 4] + f[(idx + 2) % 4] - f[(idx + 3) % 4]) % 1000000007;
If(f[idx] < 0) // Always store positive numbers
f[idx] += 1000000007;
idx = (idx + 3) %4; //In the following operation, f(n-3) is an unused value, so it is used to store f(n).
}
return idx > = 3? (int)f[idx - 3] : (int)f[idx + 1]; // You have to return it once because you gave idx = (idx + 3) % 4 at the end of the last for statement. If you don't understand, think about it when (n = 3)
}
DP problem (Memoization). However, since it is difficult to make an array of 100 million won in size, you can save memory by using the % operator.
© 2024 OneMinuteCode. All rights reserved.