When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

alphadr's blog

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

| Write comment?
»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 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

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 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 ?

»
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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
5 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