### alphadr's blog

By alphadr, 11 years ago,

Could you please tell me some problems which could be solved using matrix exponentiation on codeforces or other judges ?

Thanks.

• +3

| Write comment?
 » 11 years ago, # | ← Rev. 3 →   0
•  » » 2 months ago, # ^ |   -31 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
 » 11 years ago, # | ← Rev. 2 →   0 http://codeforces.com/gym/100199, problem E
•  » » 2 months ago, # ^ |   -31 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 ?
 » 11 years ago, # |   0
 » 11 years ago, # |   +5 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
 » 11 years ago, # |   0
 » 6 years ago, # |   0
 » 6 years ago, # |   0
 » 5 years ago, # |   +5
 » 5 years ago, # |   +6
 » 5 years ago, # | ← Rev. 3 →   0 1182E — Product Oriented RecurrenceApart from the above mentioned problem, the following problems can also be solved by matrix exponentiation.621E — Wet Shark and Blocks147B — Smile HouseHere you can read how LINK
 » 5 years ago, # |   0