Could you please tell me some problems which could be solved using matrix exponentiation on codeforces or other judges ?
Thanks.
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2024 10:57:04 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
easy hard
if you want to solve the easy one you can guess it from first solutions. if you want to solve the hard one just listen to me here: you can represent a+b√k as 2x2 matrix [a b ; kb a] . the ; ends the first row and this way you can also make matrix multiplication faster as you need only O(n*n) good luck
http://codeforces.com/gym/100199, problem E
this problem is really good wow. also D in this gym can be solved if you know matrix multiplication. but in E here is a hint : if you are at row i how do you use row i-1 ? how do you know how many times did a certain pattern exist at the past row? why is m so little m<=5 ?
http://codeforces.com/contest/222/problem/E
There is a category for Matrix Exponentiation problems in lightoj. Here is the link , i hope it will be helpful. http://www.lightoj.com/volume_problemcategory.php?user_id=8956&category=Matrix%20Exponentiation
185A - Plant
https://www.hackerearth.com/problem/algorithm/abcd-strings/description/
http://codeforces.com/problemset/problem/166/E
1117D - Magic Gems
1106F Lunar New Year and a Recursive Sequence
1182E — Product Oriented Recurrence
Apart from the above mentioned problem, the following problems can also be solved by matrix exponentiation.
621E — Wet Shark and Blocks
147B — Smile House
Here you can read how LINK
http://acm.timus.ru/problem.aspx?space=1&num=1462