Hello! I am very hard stuck with this problem form the 2024-2025 ICPC Brazil Subregional contest more specifically this.

We are given $$$N \le 10^{18}$$$ and $$$M \le 10^5$$$ pairs $$$(a_i \le 100, b_i \le 60)$$$ that we can choose any amount of time. For pair $$$i$$$ we can subtract $$$a_i$$$ form $$$N$$$ only if $$$N \% 2^{b_i} == 0$$$. Now we need to find all the different ways in which we can obtain $$$0$$$ doing these operations. (I recommend reading the statement in case I missed to specify smth.)

First it's pretty clear that we can construct a very basic dynamic programming solution that is we iterate for all numbers $$$i \le N$$$ and for each $$$i$$$ iterate over all pairs and check if $$$i \% 2^{b_j} == 0$$$ then $$$dp[i] += dp[i - a_j]$$$. This runs in $$$\mathcal{O}(N \times M)$$$.

There is also a speedup based on the fact that for a certain $$$i$$$ if there are let's say $$$cnt$$$ trailing zeros then $$$i$$$ can use all pairs with $$$b_j \le cnt$$$. So we can precompute $$$cnt[b][i]$$$ which means the number of pairs such that $$$a_j = i$$$ and have $$$b_j \le b$$$ in $$$\mathcal{O}(M \times 100)$$$ and then we can compute the answer using a generic linear recurrence based on our calculations. Overall complexity $$$\mathcal{O}((N + M) \times 100)$$$.

This is also not enough to enter our time limit. Now from our input restrictions it's pretty clear that we will need to use Matrix Exponentiation, the only problem here is that I do not see how we can do so based on the fact that we will need for each $$$i$$$ to see the number of trailing zeros. I have seen some solutions online, I did not understand how they compute the answer, so here I am asking for help.

Any similar problem(s), or hints even would be much appreciated. Thanks!

Hello! I have been stuck on this problem for a while. Here is what it asks:

Given an array, determine if it is possible to choose a set of distinct subarrays of length $$$2$$$ such that every index is taken at least once. A set of subarrays is considered distinct if no two subarrays have equal elements. For example, $$$[1,2],[1,2]$$$ is not a valid set, while $$$[1,3],[1,2]$$$ is.

As an example, let's consider the array $$$[1,2,1,2,3]$$$. We can choose $$$[1,2],[2,1],[2,3]$$$, corresponding to the indices $$$[1,2],[2,3],[4,5]$$$ (indexed from $$$1$$$).

The problem can be found here.

I have heard that this can be solved with 2SAT, but I have no idea how. I have never solved a 2SAT problem similar to this one, and I don't know what I am missing. Basically, I don't understand how to construct a graph that solves this task (or if it can be solved in another way).

Any help, similar problem(s), or hints would be much appreciated. Thanks!