Construction

Construct a set of $x,y,z$ such that, for a given $n$, $\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}$.

The construction method can be seen from the second sample.

Clearly, $n,n+1,n(n+1)$ is a valid solution. In the special case $n=1$, there is no solution, because $n+1$ and $n(n+1)$ are equal.

As for how the construction idea arises, it is probably just observing the samples together with a little number sense. This problem is not difficult for people with strong mathematical intuition.

Task 1: Determine whether it is possible to construct, and construct, a permutation of $1\dots n$ of length $n$ whose $n$ prefix sums are pairwise distinct modulo $n$.

Task 2: Determine whether it is possible to construct, and construct, a permutation of $1\dots n$ of length $n$ whose $n$ prefix products are pairwise distinct modulo $n$.

For task 1:

When $n$ is odd, no valid solution can be constructed.

When $n$ is even, a sequence of the form $n,1,n-2,3,\cdots$ can be constructed.

First, we can see that $n$ must appear in the first position of the sequence. Otherwise, the two prefix sums immediately before and after $n$ appears inevitably become equal modulo arithmetic.

Next, consider how to construct the entire sequence.

We can obtain the original sequence by constructing its prefix-sum sequence. The differences between every pair of prefix sums cannot be equal modulo arithmetic, because the difference sequence of the prefix-sum sequence corresponds to the original permutation.

Therefore, we try to construct the sequence so that its prefix-sum sequence modulo arithmetic has the form

It is not difficult to see that this perfectly satisfies all the constraints.

For task 2:

When $n$ is composite but not $4$, no valid solution can be constructed.

When $n$ is prime or equal to $4$, a sequence of the form $1,\dfrac{2}{1},\dfrac{3}{2},\cdots,\dfrac{n-1}{n-2},n$ can be constructed.

First consider when a solution exists.

Clearly, there is no solution when $n$ is composite. For a composite number, there are two smaller numbers $p,q$ such that $p\times q \equiv 0 \pmod n$, for example $(3\times6)\%9=0$. Once $p,q$ have both appeared, all subsequent prefix products remain $0$, so there is no solution for composite values. In the special case $4=2\times 2$, we can see that there are no such $p,q$, so a valid solution exists.

Now consider how to construct this sequence.

Following the same idea as in task 1, we find that $1$ must appear in the first position; otherwise, the two prefix products immediately before and after $1$ appears would be equal. Likewise, $n$ must appear in the last position, because all prefix products after the position of $n$ are $0$. After analyzing the several samples in the statement, we find that every sample has a valid solution whose prefix products are $1,2,3,\cdots,n$. Therefore, we can construct the sequence described above to satisfy this condition. It remains only to prove that these $n$ numbers are pairwise distinct.

We find that all these numbers are the inverses of $1 \cdots n-2$ $+1$, so they are distinct, and the problem is solved.

Given an integer $N$, construct an undirected graph with $N$ vertices. Let the vertex labels be $1\ldots N$; it must satisfy:

• It is a simple connected graph.
• There is an integer $S$ such that, for every vertex, the sum of the labels of its adjacent vertices is $S$.

The input is guaranteed to have a solution.

By analyzing the cases $n=3,4,5$, we can find a construction idea.

Construct a complete $k$-partite graph whose $k$ part sums are equal. Then every vertex has the same $S$, namely $\dfrac{(k-1)\sum_{i=1}^{n}i}{k}$.

If $n$ is even, pair the numbers from the two ends, namely $\{1,n\},\{2,n-1\}\cdots$.

If $n$ is odd, place $n$ alone in one group and pair the remaining $n-1$ numbers, namely $\{n\},\{1,n-1\},\{2,n-2\}\cdots$.

The connectivity of the graph constructed this way for $n\ge 3$ is easy to prove, so we omit the details.

The problem is solved.

After a hard day's work, Q fell asleep. He recalled studying 0/1 knapsack when he had just entered university. At that time, as a freshman, Q solved a simple 0/1 knapsack problem. The problem was:

Given $n$ items with volumes $v_1,v_2,…,v_n$, calculate the number of ways to choose some items (possibly none) so that the total volume is exactly $w$. Since the answer may be very large, output only the answer modulo $P$.

Because he had stayed up late solving problems for a long time, he could see only $w$ and $P$ in the sample input and that the sample output was $k$; he could not see how many items there were or the volume of each item. Even after waking up, Q could not see $n$ and $v$. Write a program to help Q recall the sample input from long ago.

This is one of the construction problems with the highest degree of freedom. This results in a situation where one has no idea how to begin.

First, it is not difficult to see that the modulus is a decoy. Since we can construct the data freely, we can certainly make the number of solutions no greater than the modulus.

In a somewhat unusual way, we realize that we can construct $n$ small items with cost $1$ and several large items with cost greater than $\dfrac{w}{2}$.

Since at most one large item can be selected, the contribution of each large item with cost $x$ to the number of solutions is $\dbinom{n}{w-x}$.

Let $f_{i,j}$ denote the minimum number of large items when there are $i$ items of cost $1$ and the number of solutions is $j$.

Precompute $f$ with dp. Calculation shows that it is sufficient to precompute all values for $i\le 20$.

The problem is solved.