Есть ли способ уменьшить сложность времени, чтобы найти эту матрицу до степени n?
Я работаю над проблемой, где я должен найти nth сила 4x4 матрица где n может быть таким большим, как 10^15 и так как значения в ответе могут быть очень большими, я могу использовать modulo 10^9+7 ,
Данная матрица
2 1 -2 -1
A= 1 0 0 0
0 1 0 0
0 0 1 0
Я написал код для этой цели, но его время выполнения больше, чем хотелось бы. Так
Кто-нибудь, пожалуйста, помогите мне в сокращении времени сложности.
#define FOR(k,a,b) for(typeof(a) k=(a); k < (b); ++k)
typedef long long ll;
#define dim 4
struct matrix {
long long a[dim][dim];
};
#define MOD 1000000007
matrix mul(matrix x, matrix y)
{
matrix res;
FOR(a, 0, dim) FOR(b, 0, dim) res.a[a][b] = 0;
FOR(a, 0, dim) FOR(b, 0, dim) FOR(c, 0, dim) {
ll temp = x.a[a][b] * y.a[b][c];
if (temp <= -MOD || temp >= MOD)
temp %= MOD;
res.a[a][c] += temp;
if (res.a[a][c] <= -MOD || res.a[a][c] >= MOD)
res.a[a][c] %= MOD;
}
return res;
}
matrix power(matrix m, ll n)
{
if (n == 1)
return m;
matrix u = mul(m, m);
u = power(u, n / 2);
if (n & 1)
u = mul(u, m);
return u;
}
matrix M, RP;
int main()
{
FOR(a, 0, dim) FOR(b, 0, dim) M.a[a][b] = 0;
M.a[0][0] = 2;
M.a[0][1] = 1;
M.a[0][2] = -2;
M.a[0][3] = -1;
M.a[1][0] = 1;
M.a[2][1] = 1;
M.a[3][2] = 1;
int nt;
scanf("%d", &nt);
while (nt--) {
ll n;
scanf("%lld", &n);
RP = power(M, n);
FOR(a, 0, dim)
FOR(b, 0, dim)
printf("%lld\n", RP.a[a][b]);
}
return 0;
}
Решение
Да. Отличный способ сделать именно то, что вы хотите, известен. Вы должны диагонализирующие матрица.
Диагонализация потребует некоторого программирования. Теория объясняется Вот, в разделе 14,6.
К счастью, существующие библиотеки матричной алгебры, такие как LAPACK, уже содержат подпрограммы диагонализации.
@ Хейл правильно и интересно отмечает, что не все матрицы диагонализуемы, что существуют вырожденные случаи. У меня нет большого практического опыта в таких случаях. Существует разложение Шура (см. Раздел 14.10 ранее связанного источника), но я обычно видел, как Шур использовал только для теоретических целей, а не для практических расчетов. Тем не менее, я верю, что Шур сработает. Я подозреваю, что для его реализации потребуется много усилий, но это сработает даже в случае строго недиагонализуемой матрицы.
Другие решения
Вы можете воспользоваться несколькими тестовыми примерами, чтобы уменьшить общее количество вычислений.
Обратите внимание, что каждый раз, когда вы вызываете power, вы пересчитываете все силы 2 вашей исходной матрицы. Таким образом, для числа, подобного 10 ^ 15 (примерно 2 ^ 50), вы получите квадрат матрицы в 50 раз, а также вычислите умножение для каждого ненулевого бита числа (возможно, 25 раз).
Если вы просто предварительно вычислите 50 степеней 2, то каждый тестовый случай потребует в среднем только 25 умножений вместо 75.
Вы можете принять эту идею немного дальше и использовать другую базу для своего возведения в степень. Это привело бы к большему количеству предварительных вычислений, но уменьшило бы умножения конечной матрицы для каждого тестового значения.
Например, вместо предварительного вычисления M ^ 2, M ^ 4, M ^ 8, M ^ 16 вы можете предварительно вычислить [M ^ 1, M ^ 2, M ^ 3], [M ^ 4, M ^ 8, M ^ 12 ], [M ^ 16, M ^ 32, M ^ 48] и поэтому M ^ 51 будет (M ^ 3) * (M ^ 48) вместо M * M ^ 2 * M ^ 16 * M ^ 32
На самом деле это не идея ускорения возведения в степень матриц, а ускорения всей программы.
Если вас просят выполнить 10 ^ 4 возведения в степень, это не значит, что они должны быть выполнены независимо. Вы можете сортировать запросы и повторно использовать предыдущий результат для каждого следующего вычисления.
Также вы можете хранить промежуточные результаты предыдущих вычислений.
detector