alphadr's blog

Matrix Exponentiation Problems ?
By alphadr, 11 years ago, In English

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

Thanks.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

easy hard

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

http://codeforces.net/gym/100199, problem E

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    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 ?

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.net/contest/222/problem/E

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

185A - Plant

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.hackerearth.com/problem/algorithm/abcd-strings/description/

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.net/problemset/problem/166/E

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

1117D - Magic Gems

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

1106F Lunar New Year and a Recursive Sequence

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://acm.timus.ru/problem.aspx?space=1&num=1462

→ Reply