P5509 Dispatch

Steve found a map in a cave. The map marked the strongholds of the dark forces, so he decided to dispatch some soldiers there.

However, these soldiers may not necessarily have the ability to fight the dark forces, so the final set of dispatched soldiers is unknown. To better understand the dispatched soldiers, Steve needs you to help compute some values. Steve has a total of $t$ armies, and each army has a different number of soldiers. Each army can be arranged into an $n \times k$ grid under a certain standard. Each soldier’s position can be represented by coordinates $(x,y)$, where $0 \le x < n$ and $0 \le y < k$. The soldier’s index is $x \cdot k + y$. The soldier at position $(0,0)$ is the captain, and will be dispatched no matter what. For the remaining soldiers, they may or may not be dispatched. The ability value of an $n \times k$ army is defined as follows: - If all soldiers are dispatched, then the ability value is $1$. - If the soldier at position $(x,y)$ (with index $i$) is not dispatched, then the ability value becomes the previous value multiplied by $\frac{x}{i-x}$. For example, for a $2 \times 2$ army, if the soldier at $(1,1)$ (index $3$) is not dispatched and all other soldiers are dispatched, then the ability value is $\frac{1}{3-1}=\frac{1}{2}$. If both the soldier at $(1,1)$ (index $3$) and the soldier at $(0,1)$ (index $1$) are not dispatched, then the ability value is $\frac{1}{3-1} \times \frac{0}{1-0} = 0$. If both the soldier at $(1,1)$ (index $3$) and the soldier at $(1,0)$ (index $2$) are not dispatched, then the ability value is $\frac{1}{3-1} \times \frac{1}{2-1} = \frac{1}{2}$. Now, for each army, Steve needs you to compute the sum of the ability values over all possible dispatch plans. To avoid fractions, output the result modulo $1145141$. If this value does not exist, output $-1$. That is, if your answer is an irreducible fraction $\frac{p}{q}$, you need to find the smallest non-negative integer $a$ such that $p \equiv q \cdot a \pmod{1145141}$, and output $a$. If no such integer exists, output $-1$. Hint: $1145141$ is a prime number.

The first line contains an integer $t$. The next $t$ lines each contain two integers $n, k$.

Output $t$ lines, each containing one integer representing the answer.

The actual value for the 4th group of testdata is $\frac{7}{3}$. The actual value for the 5th group of testdata is $\frac{55}{9}$. Explanation for the 1st group of testdata: If all soldiers are dispatched, then the ability value is $1$. If the soldier at $(1,1)$ (index $3$) is not dispatched, then the ability value is $\frac{1}{3-1}=0.5$. If the soldier at $(0,1)$ (index $1$) is not dispatched, then the ability value is $\frac{0}{1-0} = 0$. If both the soldier at $(1,1)$ (index $3$) and the soldier at $(0,1)$ (index $1$) are not dispatched, then the ability value is $\frac{1}{3-1} \times \frac{0}{1-0} = 0$. If the soldier at $(1,0)$ (index $2$) is not dispatched, then the ability value is $\frac{1}{2-1} = 1$. If both the soldier at $(1,0)$ (index $2$) and the soldier at $(1,1)$ (index $3$) are not dispatched, then the ability value is $\frac{1}{2-1} \times \frac{1}{3-1}=0.5$. If both the soldier at $(1,0)$ (index $2$) and the soldier at $(0,1)$ (index $1$) are not dispatched, then the ability value is $\frac{1}{2-1} \times \frac{0}{1-0}=0$. If only the captain is dispatched, then the ability value is $\frac{1}{3-1} \times \frac{0}{1-0} \times \frac{1}{2-1}=0$. So, the answer is $1+0.5+0+0+1+0.5+0+0=3$. Constraints: For all testdata, $n \ge 1, k \ge 2$. Subtask 1 is the testdata used during the contest: Test point | Score | $t$ | $n \le$ | $k \le$ :-: | :-: | :-: | :-: | :-: 1 | 10 | 5 | 5 | 5 2 | 11 | 100 | 100 | 100 3 | 12 | 100000 | 5 | 100000 4 | 13 | 100000 | 100000 | 5 5 | 16 | 5 | 100000 | 100000 6 | 18 | 5 | $10^9$ | $10^9$ 7 | 20 | 100000 | $10^9$ | $10^9$ Subtask 2 includes two unscored hack testdata, both satisfying $t=1$. #8 satisfies the properties of #7. #9 satisfies the properties of #5. Translated by ChatGPT 5