P7704 "MCOI-09" Greedy Deletion

Positive integers less than or equal to $n$ form the set $S_n=\{1,2,\dots,n\}$. The cost to delete the element with value $i$ is $i^k$, and each element can be deleted at most once. Given positive integers $n$ and $k$, find: what is the minimum cost to make the product of all elements in $S_n$ a perfect square? Output the answer modulo $998244353$. **Note that you need to minimize the cost first, then take modulo $998244353$, rather than minimizing the cost after taking modulo $998244353$.** You need to answer $T$ queries, and all queries share the same $k$.

The first line contains three positive integers $T$, $k$, and $\max n$, representing the number of queries, the given $k$, and the maximum $n$. The next $T$ lines each contain one positive integer $n$.

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th query.

#### Explanation for Sample 1 For $n=1$, the product of $S_1$ is a perfect square, so no deletion is needed. For $n=6$, you can delete $5$ to make the product of $S_6$ a perfect square. #### Constraints - Subtask 1 (7 pts): $\max n\le 20$. - Subtask 2 (37 pts): $\max n\le 1000$. - Subtask 3 (11 pts): $T\le 1000$. - Subtask 4 (45 pts): no additional constraints. For $100\%$ of the testdata, $1\le \max n\le 5\times 10^6$, $1\le T\le 5\times 10^5$, $1\le k< 998244353$. It is **guaranteed** that $1\le n\le \max n$. Translated by ChatGPT 5