Matrix Exponentiation

9 problems from Matrix Exponentiation (contest 102644), difficulty -. 6/9 solutions verified against sample I/O.

9 items

Matrix Exponentiation

Special | 9 problems | 6/9 verified | Difficulty - | 17m 12s

#	Problem	Time	✓
A	Random Mood	3m 47s	✓
B	String Mood	2m 26s
C	Fibonacci	41s
D	Count Paths	50s	✓
E	Knight Paths	5m 52s	✓
F	Min Path	33s
G	Recurrence With Square	58s	✓
H	String Mood Updates	1m 1s	✓
I	Count Paths Queries	1m 4s	✓

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644B - String Mood

I can write the editorial, but the problem statement you provided is empty. I found that Codeforces Gym 102644B “String Mood” is the problem where Limak starts happy, reads an uppercase string, and the task is to count strings of length n that leave him happy, with n up to…

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644C - Fibonacci

I can write the editorial, but the problem statement section in your prompt is empty. I looked up Codeforces 102644C, and it is the problem asking for the n-th Fibonacci number modulo $10^9+7$, where $0 le n le 10^{18}$.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644H - String Mood Updates

We maintain a string of uppercase letters and question marks. A question mark can later become any uppercase English letter. Reading the string from left to right changes Limak's mood, which has only two possible states: happy and sad.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644F - Min Path

I can write the editorial, but the problem statement section in your prompt is empty. I found that Codeforces 102644F “Min Path” is a graph problem about finding the minimum total weight of a path with exactly k edges, where k can be as large as 10^9, and the intended…

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644D - Count Paths

The problem gives a directed graph with vertices numbered from 1 to n and asks for the number of possible walks that use exactly k directed edges. A walk may reuse vertices and edges, so the task is not about simple paths.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644G - Recurrence With Square

The sequence in this problem is not a standard linear recurrence because the next value depends not only on previous values, but also on the current position in the sequence.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644I - Count Paths Queries

The problem describes a directed graph with up to 200 vertices. A path is a sequence of exactly k directed edges, and vertices or edges may appear more than once.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644E - Knight Paths

We have an 8 by 8 chessboard and a knight placed on the top-left square. A path is a sequence of visited squares where every consecutive pair is connected by a legal knight move.

Practice › Codeforces Solutions › Matrix Exponentiation ›

CF 102644A - Random Mood

The problem describes a person whose mood has only two possible states: happy and sad. Every second, the current mood may change with probability p, or stay the same with probability 1 - p.