A - 01 Matrix Again

Hint 1

Let’s consider the solution when \(M=1\).

Hint 2

Let’s consider the solution when the first condition is not present.

Hint 3

Let’s try combining the above two solutions.

---

B - Simple Math 4

Hint 1

By performing algebraic transformations, you can reduce it to a case where \(N\) is smaller than it currently is.

Hint 2

What happens when you subtract \(2^{N-M}(2^M - 2^K)\) from \(2^N\)?

Hint 3

If \(N\) is less than \(M\), in most cases the answer is \(2^N \bmod 10\).

---

C - Max Permutation

Hint 1

Consider the solution when all \(C_i\) are equal.

Hint 2

How can the algorithm obtained from the solution when all \(C_i\) are equal be applied to the general case?

Hint 3

It can be applied to the general case by applying it in descending order of \(C_i\).

---

D - Swap Permutation

Solution 1

Hint 1

Redefine \(|P_i - P_{i+1}|\) as the number of integers \(k\) that satisfy \(\min(P_i,P_{i+1}) \le k < \max(P_i,P_{i+1})\).

Hint 2

Using the above, you can transform this problem into one that only involves \(0\) and \(1\) by converting values less than or equal to \(k\) to \(0\) and values greater than \(k\) to \(1\). (Do this for all \(k\) and take the sum of the answers.)

Hint 3

The version of the problem that only involves \(0\) and \(1\) can be solved using matrix exponentiation.

Solution 2

Hint 1

Let’s find the number of sequences of operations where \(P_i\) and \(P_j\) are adjacent after the operations.

Hint 2

The above only depends on whether \(i = 1\) or not, whether \(i + 1 = j\) or not, and whether \(j = N\) or not.

Hint 3

The number of pairs \((i,j)\) that satisfy any of the above three conditions is \(\mathrm{O}(N)\).

---

E - Max Vector

Hint 1

You can solve this problem by using the minimum cut.

Hint 2

There are \(\max A\) possible values for \(X_i\), so let’s create vertices for all of them. Then, you can reduce this problem to a minimum cut.

---

F - Colorful Star

Hint 1

You can create most trees.

Hint 2

Let’s determine whether a certain tree can be created by looking at the operations in reverse.

Hint 3

The number of pairs of adjacent vertices with the same color is important.

Hint 4

The colors of the vertices at depth \(1\) are also important.