Рекурсив хамаарал, Матриц ашиглан N-р гишүүнийг Log-д олох

Бид рекуррент харьцаатай бодлого бодож байхдаа N-аар гишүүнийг DP ашиглан O(N)-д олдог. Гэвч зарим тохиолдолд хугацааны хязгаарлалт маш бага байхад 10^6-р гишүүнийг P модуль жиш гэсэн бодлогууд гарч ирдэг. Жишээ нь Фибаночийн дарааллын N-р гишүүнийг (1<=N<=1000000000) % 999983 мөн саяны Үндэсний олимпиадад бодогдсон Маяабоначийн тоо бодлого.



Энэ постыг та уншихаасаа өмнө Матрицын талаар зохих мэдлэгтэй, үржих, нэмэх хасах үйлдэлүүдийг хийж чаддаг байх ёстой шүү!



Ерөнхий тохиолдол:

Бид өгөгдсөн эсвэл өөрийн олсон рекуррент харьцаагаа ашиглан дараах шинэ харьцааг гаргаж авна.
X(i+1) = M*X(i) Энд X нь Кх1 хэмжээтэй матриц, М нь КхК хэмжээтэй тогтмол утгатай матриц. Бид тэгэхээр рекуррэнт харьцаагаа ашиглан М матрицыг олох ёстой.

  X(i+1)              X(i)
| f(n+1)   |       | f(n)   |
|  f(n)    |       | f(n-1) |
| f(n-1)   | = M x | f(n-2) |
| ......   |       | ...... |
| f(n-k+1) |       | f(n-k) |

Бодлогуудыг ерөнхийд нь дараах хэдэн төрөлд хувааж болно.



#1::

Хамгийн энгийн буюу рекуррент харьцаа дараах хэлбэрийнх байж болно.

f(n) = f(n-1) + f(n-2). Үүнийг дараах байдлаар бичиж болно. f(n+1) = f(n) + f(n-1). Тэгвэл X(i+1) болон X(i) матрицууд
дараах байдлаар бичигдэнэ.

  X(i+1)           X(i)
| f(n+1) | = M x | f(n)   | => | f(n+1) | = | a b | x | f(n)   |
| f(n)   |       | f(n-1) |    | f(n)   |   | c d |   | f(n-1) |

Тэгэхээр харж байгаа байх, К-г олохдоо тухайн харьцаа өөрөөсөө өмнөх хэдэн гишүүнээсээ хамаарч байна, тэдгээрийн гишүүдийн тоотой тэнцүү байх нь. Фибаночийн хувьд өмнөх 2 гишүүнээсээ хамаардаг тул бидний матрицууд X(Kx1), M(KxK) байх нь. Одоо М матрицыг олъё. Дээрх тэгшитгэлийн баруун талын 2 матрицыг үржүүлээд бодохоор бид дараах 2 тэгшитгэлийг гаргаж чадна.

a*f(n) + b*f(n-1) = f(n+1)

c*f(n) + d*f(n-1) = f(n) . Дарааллыхаа эхний 3-н гишүүнийг мэдэх учир орлуулаад бодохоор a=1, b=1, c=1, d=0 гэж гарна.

Одоо бид М-г мэдэх учраас дараах байдлаар бичиж болно.

| f(n+1) | = | 1 1 | x | f(n)   |
| f(n)   |   | 1 0 |   | f(n-1) |

#2::

Рекуррент харьцаа дараах хэлбэртэй байж болно. f(n) = a * f(n-1) + b * f(n-2). a, b тогтмол тоо. Дараах хэлбэртэй тэнцүү f(n+1) = a * f(n) + b * f(n-1).

Бидний олох матрицууд К нь 2 гэдгийг хялбархан харж байгаа байх. Өмнөхтэй адилхан энгийн алгебр бодоод дараах харьцаагаа гаргана.

| a   b | x |  f(n)  | = | f(n+1) |
| 1   0 |   | f(n-1) |   |  f(n)  |

#3::

f(n) = a * f(n-1) + c * f(n-3). Энд f(n-2) байхгүй үед яах вэ? Энэ дараах формтой тэнцүү.

f(n) = a * f(n-1) + 0 * f(n-2) + c * f(n-3) = f(n+1) = a * f(n) + 0 * f(n-1) + c * f(n-2)

| a  0  c |   |  f(n)  |   | f(n+1) |
| 1  0  0 | x | f(n-1) | = |  f(n)  |
| 0  1  0 |   | f(n-2) |   | f(n-1) |.

#4::

f(n) = a*f(n-1) + b*f(n-2) + c, С дурын тогтмол тоо.

| f(n+1) | = | a b 1 | x | f(n)   |
| f(n)   |   | 1 0 0 |   | f(n-1) |
| c      |   | 0 0 1 |   | c      |

#5::

Зарим тохиолдолд И тэгш үед ийм, сондгой үед ийм гэхчихлэн өөр өөр нөхцөлтэй байдаг. Энэ үед аль ч тохиолдолд нь 2 өөрөөр бодолт хий.

#6::

Рекуррент харьцаа 2 өөр функцээр тодорхойлогдож болно.

g(n) = a*g(n-1) + b*g(n-2) + c*f(n), f(n) = d*f(n-1) + e*f(n-2).

| g(n+1) |   | a b c 0 |   | g(n)   |
| g(n)   | = | 1 0 0 0 | x | g(n-1) |
| f(n+2) |   | 0 0 d e |   | f(n+1) |
| f(n+1) |   | 0 0 1 0 |   | f(n)   |

За ерөнхийдөө ойлгомжтой гэж бодож байна. Ингээд М матрицаа олцон тохиодолд яах вэ?

X(i+1) = M*X(i). Хоёр талыг хоюуланг нь М-д үрж.



M * X(i+1) = M * M * X(i)

X(i+2) = M^2 X(i)

..

X(i+k) = M^k * X(i)

Бид 2 матрицыг O(N^3)-д үрждэг. Тэгвэл К зэргийг шугаман олвол O(N^3*K). Хэрвээ бид К зэргийг Log-д олж чадвал O(N^3*LogK) хангалттай хурдан олж чадахнээ. Одоо зэргийг хэрхэн Log-д олохыг харъя.
a^k олох байг.

- Хэрэв К 0 бол мэдээж 1

- Хэрэв К тэгш тоо байвал a^k = (a(k/2)*a(k/2))

- Хэрэв К сондгой байвал a^k = (a(k-1)*a)

Үүнийг С++ дээр бичвэл:

int p(int n, int k){
    int ret = 1;
    if(k==0)return ret;
    if(k==1)return n;
    if(k%2==0) ret *= p(n, k/2)*p(n, k/2);
    else ret *= p(n, k/2)*p(n, k/2)*n;
    return ret;
}

Маяабоначийн Тоо бодлого бол дээрх формоос 3дугаар форм-д нь орох бодлого. М матрицаа ерөнхийдөө аналитик байдлаар гаргана. М матрицын эхний мөрний a болон b дэх багана дахь тоо 1 бусад нь 0. Бусад мөрийн (i-1)-р тоо нь 1 бусад нь 0 гэж матрицаа үүсгэнэ. Бодолт O(B^3 * LogN)-д шийдэгдэнэ.