Матричное возведение - действительно верный путь, но предстоит еще немного поработать.
Поскольку g(n) не является постоянным значением, нет способа применить матричное возведение (O(log n) вместо O(n)) к рекуррентному отношению в его текущей форме.
Подобное рекуррентное отношение необходимо найти для g(n) только с постоянным конечным термином,Поскольку g(n) является кубическим, требуются 3 рекурсивных члена:
g(n) = x*g(n-1) + y*g(n-2) + z*g(n-3) + w
Разверните кубические выражения для каждого из них:
n³ + n² = x(n³-2n²+n) + y(n³-5n²+8n-4) + z*(n³-8n²+21n-18) + w
= n³(x+y+z) + n²(-2x-5y-8z) + n(x+8y+21z) + (w-4y-18z)
Сопоставьте коэффициенты, чтобы получить три уравнения для одновременного x, y, z плюс еще один для вычисления w:
x + y + z = 1
-2x - 5y - 8z = 1
x + 8y + 21z = 0
w - 4y - 18z = 0
Решите их, чтобы получить:
x = 3 y = -3 z = 1 w = 6
Удобно, что эти коэффициенты также являются целыми числами *, что означает, что модульная арифметика может выполняться непосредственнона повторение.
* Я сомневаюсь, что это было совпадением - вполне могло быть намерение экзаменатора по найму.
Матричное уравнение повторения поэтому:
| a b c 1 0 0 0 | | f(n-1) | | f(n) |
| 1 0 0 0 0 0 0 | | f(n-2) | | f(n-1) |
| 0 1 0 0 0 0 0 | | f(n-3) | | f(n-2) |
| 0 0 0 3 -3 1 6 | x | g(n) | = | g(n+1) |
| 0 0 0 1 0 0 0 | | g(n-1) | | g(n) |
| 0 0 0 0 1 0 0 | | g(n-2) | | g(n-1) |
| 0 0 0 0 0 0 1 | | 1 | | 1 |
Окончательное уравнение возведения в степень матрицы:
[n-2]
| a b c 1 0 0 0 | | f(2) | | f(n) | | f(2) | | r |
| 1 0 0 0 0 0 0 | | f(1) | | f(n-1) | | f(1) | | q |
| 0 1 0 0 0 0 0 | | f(0) | | f(n-2) | | f(0) | | p |
| 0 0 0 3 -3 1 6 | x | g(3) | = | g(n+1) | , | g(3) | = | 36 |
| 0 0 0 1 0 0 0 | | g(2) | | g(n) | | g(2) | | 12 |
| 0 0 0 0 1 0 0 | | g(1) | | g(n-1) | | g(1) | | 2 |
| 0 0 0 0 0 0 1 | | 1 | | 1 | | 1 | | 1 |
(Каждая операция неявно по модулю 10^9 + 7 или в зависимости от того, какое число предоставлено.)
Обратите внимание, что оператор % в Java - это остаток , который отличается от модуля для отрицательных чисел.Пример:
-1 % 5 == -1 // Java
-1 = 4 (mod 5) // mathematical modulus
Обходной путь довольно прост:
long mod(long b, long a)
{
// computes a mod b
// assumes that b is positive
return (b + (a % b)) % b;
}
Оригинальный итерационный алгоритм:
long recurrence_original(
long a, long b, long c,
long p, long q, long r,
long n, long m // 10^9 + 7 or whatever
) {
// base cases
if (n == 0) return p;
if (n == 1) return q;
if (n == 2) return r;
long f0, f1, f2;
f0 = p; f1 = q; f2 = r;
for (long i = 3; i <= n; i++) {
long f3 = mod(m,
mod(m, a*f2) + mod(m, b*f1) + mod(m, c*f0) +
mod(m, mod(m, i) * mod(m, i)) * mod(m, i+1)
);
f0 = f1; f1 = f2; f2 = f3;
}
return f2;
}
Матричные функции по модулю:
long[][] matrix_create(int n)
{
return new long[n][n];
}
void matrix_multiply(int n, long m, long[][] c, long[][] a, long[][] b)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long s = 0;
for (int k = 0; k < n; k++)
s = mod(m, s + mod(m, a[i][k]*b[k][j]));
c[i][j] = s;
}
}
}
void matrix_pow(int n, long m, long p, long[][] y, long[][] x)
{
// swap matrices
long[][] a = matrix_create(n);
long[][] b = matrix_create(n);
long[][] c = matrix_create(n);
// initialize accumulator to identity
for (int i = 0; i < n; i++)
a[i][i] = 1;
// initialize base to original matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
b[i][j] = x[i][j];
// exponentiation by squaring
// there are better algorithms, but this is the easiest to implement
// and is still O(log n)
long[][] t = null;
for (long s = p; s > 0; s /= 2) {
if (s % 2 == 1) {
matrix_multiply(n, m, c, a, b);
t = c; c = a; a = t;
}
matrix_multiply(n, m, c, b, b);
t = c; c = b; b = t;
}
// write to output
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
y[i][j] = a[i][j];
}
И, наконец, сам новый алгоритм:
long recurrence_matrix(
long a, long b, long c,
long p, long q, long r,
long n, long m
) {
if (n == 0) return p;
if (n == 1) return q;
if (n == 2) return r;
// original recurrence matrix
long[][] mat = matrix_create(7);
mat[0][0] = a; mat[0][1] = b; mat[0][2] = c; mat[0][3] = 1;
mat[1][0] = 1; mat[2][1] = 1;
mat[3][3] = 3; mat[3][4] = -3; mat[3][5] = 1; mat[3][6] = 6;
mat[4][3] = 1; mat[5][4] = 1;
mat[6][6] = 1;
// exponentiate
long[][] res = matrix_create(7);
matrix_pow(7, m, n - 2, res, mat);
// multiply the first row with the initial vector
return mod(m, mod(m, res[0][6])
+ mod(m, res[0][0]*r) + mod(m, res[0][1]*q) + mod(m, res[0][2]*p)
+ mod(m, res[0][3]*36) + mod(m, res[0][4]*12) + mod(m, res[0][5]*2)
);
}
Вот некоторые примеры тестов для обоих алгоритмов выше.
Оригинальный итерационный алгоритм:
n time (μs)
-------------------
10^1 9.3
10^2 44.9
10^3 401.501
10^4 3882.099
10^5 27940.9
10^6 88873.599
10^7 877100.5
10^8 9057329.099
10^9 91749994.4
Новый матричный алгоритм:
n time (μs)
------------------
10^1 69.168
10^2 128.771
10^3 212.697
10^4 258.385
10^5 318.195
10^6 380.9
10^7 453.487
10^8 560.428
10^9 619.835
10^10 652.344
10^11 750.518
10^12 769.901
10^13 851.845
10^14 934.915
10^15 1016.732
10^16 1079.613
10^17 1123.413
10^18 1225.323
Старому алгоритму потребовалось более 90 секунд, чтобы вычислить n = 10^9, в то время как новый алгоритм выполнил его всего за 0,6 милли секунд (ускорение в 150 000 раз)!
Время оригинального алгоритмасложность была явно линейной (как и ожидалось);n = 10^10 заняло слишком много времени, поэтому я не продолжил.
Очевидно, что сложность времени нового алгоритма была логарифмической - удвоение порядка n привело к удвоению времени выполнения (опять-таки, как и следовало ожидать из-за возведения в квадрат в квадрате).
Для «малых» значений n (< 100) накладные расходы на размещение матрицы и операции затмевают сам алгоритм, но быстро становятся незначительными по мере увеличения n.