Алгоритм програмчлал.

Шинэ жил боллоо. Гэсэн ч ахиад л зэрэг. Өнөөх л a^b%mod-оо бодоцгооё. Бид хувиргалт хийгээд a, b < mod болгож чадна. Харин mod <= 10^13 гэвэл a^b бодох явцад үржвэр нь хамгийн ихдээ ойролцоогоор 10^26 болох юм. Гэтэл long long төрөлд үүнийг хийж чадах билүү? Тэгхээр өмнөх бодолтууд зөв биш гэдгийг анзаарсан байх. Үүнийг хэрхэн шийдэх вэ? Асуудал нь үржих үйлдэл нь том тооны хувьд асуудалтай байгаа тул үүнийг зөв олох хэрэгтэй. x*(y/2)%mod -г мэдэж байхад бид x*y олж чадна. Өмнө нь ашиглаж байсан санаа буюу a^b олсон бодлоготой адил болж байна.

Backtrack-н тухай. Бидэнд нэг граф өгөгдсөн гэж үзье. Мөн X, Y гэсэн хоёр тоо өгөгдөх ба энэ нь X оройгоос Y орой хүрэх бүх боломжит замыг хэвлэ гэсэн бодлого байг. Энэ замд нэг орой нэг л удаа орно. Энэхүү бодлогыг DFS ашиглан бодоцгооё. Эхлээд vis[U] = 1 байвал U гэсэн орой нь одоо явж байгаа замд орсон гэж үзье. Эсрэг тохиолдолд ороогүй. Хэрхэн бид замаа хадгалах вэ? S[] гэсэн массивын эхний  элемент  гэдэг нь одоо явж байгаа замын эхний орой,  дараагийн   элемент  нь дараагийн орой гэх мэт хадгална. Тэгвэл энэ замд хэдэн орой орсныг хадгалах cnt гэсэн тоог  авъя . Эхлээд cnt = 0, vis- ын  бүх утга 0 байна. X оройгоос гүний нэвтрэлтээ хийж эхэлье. dfs нь одоо U орой дээр явж байгаа гэж үзье. Хэрвээ энэ орой нь Y оройтой ижил бол бид нэг зам олж чадсан гэсэн үг ба S[1], S[2], ..., S[cnt] хүртэлх бүх оройг хэвлэх ба энэ нь бидний зам. Нэмээд Y оройг хэвлэнэ. Учир нь энэ замд U оройгоо бид нэмээгүй байгаа. Эсрэг тохиолдолд S[cnt+1]=U, vis[U] = 1 болн...

Хоёртын хайлт(binary search) гэх алгоритмын тухай бичнэ. Энэ удаад энгийн нэг бодлого дээр ярилцъя.  Бодлого . Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал байгаа гэж бодъё. Мөн Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9. Анализ: Энгийн давталт ашиглан олж болно. Тэгвэл хугацаа хамгийн ихдээ Q*N болох юм. Энэ нь 10^10 ба маш их үйлдэл хийж байгаа юм. Тэгвэл хэрхэн хурдан шийдэх вэ? Анхаарах зүйл нь энэ дараалал өсөхөөр эрэмбэлэгдсэн байгаа. Бид одоо X гэсэн тоог энэ дараалалд байгаа эсэхийг олох гэж байгаа гэж бодъё. Тэгвэл энэ дарааллын голын элементийн утгыг бид 1 үйлдлээр мэдэж чадна. Энэ элементийг индекс нь mid=(n+1)/2 болох ба энд 3 салах юм. a[mid] == X бол бид шууд байгаа гэдгийг нь олж чадлаа. a[mid] > X бол (mid, mid+1,..., n) хүртэлх индекстэй бүр элемент нь бидний хайж байгаа тооноос эрс их нь ...

Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13. Бид энгийн давталт ашиглан үүнийг олж чадах юм. Гэвч үүнийг олохын тулд B үйлдэл хийх ба энэ нь 10^13 тул маш удаан ажиллана. Үүнийг хэрхэн хурдан хугацаанд шийдэх вэ? B тоо нь хоёртын бичиглэлдээ B=x[0]*(2^0)+x[1]*(2^1)+...+x[k]*(2^k) гэж задардаг байг. Тэгвэл k<=log(10^13) байх юм. Тэгвэл бид A^1, A^2, A^3, ... , A^k гэх мэт k ширхэг тоонуудыг k үйлдлээр байгуулна. Одоо энэ хоёрыг угсарвал A^B=(A^(x[0]*(2^0)))*(A^(x[1]*(2^1)))*...*(A^(x[k]*(2^k))) болох юм. Ингэснээр бид k үйлдлээр A тооны B зэргийг олж чадаж байна. Хэрвээ B тоо нь тэгш бол A^B=(A^(B/2))*(A^(B/2)) харин сондгой үед A^B=(A^(B/2))*(A^(B/2))*A гэдэг нь тодорхой юм. Эндээс бид A тооны B зэргийг мэдэхийг хүсвэл A тооны B/2 зэргийг мэдэж байхад олж чадна гэдэг нь харагдаж байна. Тэгвэл A тооны...