Overflow in case of small $$$t$$$ values. When we count the number of parts that we can produce in $$$\frac{10 ^ {18}}{2}$$$ minutes, the answer will be about $$$10 ^ 5 * 10 ^ {18}$$$

Could you please elaborate, how you came up with the formula for $$$f[a] [b]$$$?

I will describe the combinatorial idea of H here.

Consider a digraph of $$$(a + b)$$$ vertices $$$1, \dots, a, a + 1, \dots, a + b$$$.

• For each $$$1 \leq i < a + b$$$, there is an edge $$$i \to i + 1$$$.
• For each $$$1 \leq i \leq a + b$$$, there are $$$x$$$ self-loops $$$i \to i$$$.
• For each $$$a + 1 \leq i \leq a + b$$$, there are $$$(y - x)$$$ self-loops $$$i \to i$$$. There loops are called special.

Now, $$$f(a, b)$$$ is the number of paths of length $$$(n + 1)$$$ from $$$1$$$ to $$$a + b$$$. Consider one of such paths.

• If it doesn't pass through any special loop on vertex $$$a + 1$$$, the number of ways is $$$f(a + 1, b - 1)$$$.
• Otherwise, we can split the path at its first encounter, it's $$$(y - x) f(a + 1, b)$$$.

Therefore, we have $$$f(a, b) = f(a + 1, b - 1) + (y - x) f(a + 1, b)$$$. Or equivalently, $$$f(a, b) = \frac{f(a - 1, b).- f(a, b - 1)}{y - x}$$$.

G: The answer for the first $$$i$$$ nodes is always going to be of the form of 2 paths: one path $$$a_0$$$, which is made up of only edges with 0s written on them, and another path $$$a_1$$$, which is made up of only edges with 1s written on them. Let the $$$i$$$-th node of $$$a_0$$$ be $$$a_{0,i}$$$, and the $$$i$$$-th node of $$$a_1$$$ be $$$a_{1,i}$$$. Let the length of $$$a_0$$$ be $$$l_0$$$, and the length of $$$a_1$$$ be $$$l_1$$$. It will always be true that $$$a_{0,1}=a_{1,1}$$$ and $$$a_{0,l_0}=a_{1,l_1}$$$, meaning that those paths always start and end at the same node. It is also possible that $$$l_0=1$$$, meaning that the answer is a cycle of 1s, or that $$$l_1=1$$$, meaning that the answer is a cycle of 0s.

When adding node $$$i+1$$$, by looking at the cases where $$$l_0=1$$$ based on $$$C_{i+1,a_{1,1}}$$$ and $$$C_{i+1,a_{1,2}}$$$, $$$l_1=1$$$ based on $$$C_{i+1,a_{0,1}}$$$ and $$$C_{i+1,a_{0,2}}$$$ and $$$l_0,l_1>1$$$ based on $$$C_{i+1,a_{0,1}}$$$, $$$C_{i+1,a_{1,2}}$$$ and $$$C_{i+1,a_{0,2}}$$$ you can always find a way to add $$$i+1$$$ to the answer.

J: Let $$$\mathrm{dp}[l][r][a][b]$$$ be the solution to the problem if we are only allowed to include the elements that are in positions $$$l \ldots r$$$ and have value in $$$a \ldots b$$$, such that the maximum value we pick is exactly $$$b$$$. To calculate it, notice that we only have one position $$$m$$$ where the array has value $$$b$$$. If we include it, the maximum of the elements with positions $$$l \ldots m - 1$$$ must be less than the minimum of the elements with positions $$$m + 1 \ldots r$$$. We can now calculate the dp by iterating over al possible maximum values of the left side. The complexity is $$$O(n^5)$$$ but it has a very small constant.

G: There are probably many constructions but here is mine. I interpret the input as a graph, with 1 meaning "edge" and 0 meaning "no edge".

Let's consider the spanning forest obtained by DFS. It is always possible to remove some path from the root of a tree down to some vertex of the same tree, such that after removing, no connected component will contain more than half (rounded up) of the remaining vertices. You can prove this with a greedy argument, similar to the existence of a centroid. This removed path will be the first part of the permutation we are asked to find.

For the second part, remove vertices from the remaining connected components so that you will never take from the same component in a row. This is kind of a well-known problem. The removed vertices in the order you remove them form the second part of the permutation. Since the original spanning forest was constructed by DFS and the construction of the permutation does not allow you to take a descendant or ancestor of a vertex right after picking a vertex, we can be sure that adjacent vertices in the permutation are not connected by an edge.

Finally, if the first vertex you removed in the first part happens to be from the same tree as the last vertex you removed in the second part, you may need to perform a cyclic shift.

The model solution starts from this idea. We optimize it into $$$O(\mathrm{len}^2)$$$.

We know the DP before the contest, but it's super hard (and somehow unfair) to distinguish between these two solution by their constant.

You just take the intersection of halfspaces from the library and that's it ¯\_(ツ)_/¯ /s

At the start you ensure that $$$x_1<x_2$$$ etc. by possibly negating these.

Let us define an octant as a part of space satisfying $$$x \ge a, y \ge b, z \ge c$$$ for some (a, b, c). You express this intersection through incl-excl principle on 8 octants, so the task is reduced to computing the volume of the intersection of this tetrahedron with one octant. However this tetrahedron is an intersection of an octant with a halfspace, so we may as well first intersect these two octants to get another octant and now we just need to compute the intersection of one octant with that halfspace. This is easily doable if we compute lengths of sides of resulting tetrahedron what is done by moving our point in each of 3 directions and computing ratios of some determinants.

And here is my clean code: https://ideone.com/baWvxN

No. It was held by a offline domjudge server.

No. The model solution consumes $$$O(m)$$$ memory.

Ok i now can solve the whole problem with $$$O(1)$$$ memory

Calculate $$$f(0)$$$ with prefix function. For $$$k > 0$$$ it's easy to see that $$$f(k)$$$ equals either $$$k + m$$$ or $$$f(p(k))$$$, where $$$p$$$ is prefix function of $$$s$$$.

If n > 1 then x divides b, you can check all pairs (x, b) (there is at most 1 corresponding a). If n = 1 then if k = 1 answer is 2m(2m + 1), otherwise 0.