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

Thanks.

# | User | Rating |
---|---|---|

1 | jiangly | 3678 |

2 | Benq | 3602 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3541 |

5 | cnnfls_csy | 3540 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Geothermal | 3409 |

9 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | TheScrasse | 161 |

3 | SecondThread | 161 |

3 | awoo | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 156 |

9 | BledDest | 145 |

9 | Geothermal | 145 |

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

Thanks.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2024 03:23:37 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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