P4233 Aya Shameimaru's Notes

(7) Goodbye, friends in the Underworld. We have stayed in the Palace of the Earth Spirits for many days. During these days, Satori shared many stories about the Former Hell. This trip underground has been very fulfilling. Although we are still a bit reluctant to leave, humans must see the sun after all, and it would be a burden to keep troubling Satori to host us. Well then, let us say goodbye to Satori, Koishi, Orin, Okuu, and the other pets. ... Snow is still drifting over the streets of Former Hell. We can already see the karst cave. The environment is becoming enclosed again. Eh, isn’t that the mountain woman ahead? “Ah, you are returning to the surface? How was it?” “It was great. By the way, the remaining problem has been solved.” We explained to the mountain woman the method we heard from Nitori. “Thanks!” “You’re welcome. See you~” The world is a vast white... The sunlight is so dazzling that it takes several minutes before we can open our eyes to see the scenery on the surface. We follow the path through the Magic Forest toward the shrine. This journey comes to an end with the sound of our footsteps. Suddenly, a torn page appears on the ground ahead. Picking it up, we find that it fell out of Aya’s notebook. Aya Shameimaru (Shameimaru Aya), being a (not-so-reliable) reporter, noticed that the pets in the Palace of the Earth Spirits would sometimes fight each other, so she wrote down the win–loss relationships for each duel in her notebook. On the page we just picked up, several “single round-robin tournaments” are recorded. Each round-robin tournament is abstracted as a tournament graph, where vertices represent pets participating in the round robin, and a directed edge from vertex $u$ to vertex $v$ means that pet $u$ defeated pet $v$ in a match. Observing that every tournament on this page contains at least one cycle that visits all vertices, we guess Aya records only such tournaments. Perhaps because Aya was unsure who could beat whom, she left a question at the very bottom of that page... (See Problem Description.) This last question is for you to solve. The Great Hakurei Barrier is already behind us. We hope this trip underground leaves you with warm memories. (The End.)

If a tournament contains a Hamiltonian cycle, then we call this tournament “worth recording.” Choose uniformly at random from all “worth recording” tournaments with $n$ pairwise distinct vertices. Find the expected number of Hamiltonian cycles in the chosen tournament. Since the answer may be too large or lose precision, you only need to output the answer modulo $998244353$. That is: let the answer be $\frac{q}{p}$. You must output an integer $x$ such that $p x \equiv q \bmod 998244353$ and $0 \leqslant x < 998244353$. It can be proved that such an $x$ exists and is unique. If no such tournament exists, output `-1`.

One line with a positive integer $n$.

Output $n$ lines. On line $i$, print the answer for input $i$.

Sample explanations: - When $n=1$, there is only one tournament, which is a single vertex. - When $n=2$, the tournament has only one edge and cannot form a Hamiltonian cycle. - When $n=3$, there are two “worth recording” tournaments, namely $1\to2\to3\to1$ and $1\to3\to2\to1$, each having exactly $1$ Hamiltonian cycle, so the expected value is $1$. - When $n=4$, there are many “worth recording” tournaments (too many to list here), but all that satisfy the condition are isomorphic, so the expected value is $1$. Constraints: - In test points 1–3, $n \leqslant 7$. - In test points 4–6, $n \leqslant 10$. - In test points 7–10, $n \leqslant 1000$. - In test points 11–16, $n \leqslant 10000$. - In test points 17–25, $n \leqslant 100000$. The testdata has a gradient; each test point is worth 4 points. To avoid constant-factor issues, the last two points have a 2 s time limit. Terminology: - Tournament: https://en.wikipedia.org/wiki/Tournament_(graph_theory) - Hamiltonian cycle: https://en.wikipedia.org/wiki/Hamiltonian_cycle by oscar Translated by ChatGPT 5