P8941 [DTOI 2023] D. Goodbye 2022

> I announce with fireworks, say goodbye with a wave, and give thanks with a bow. Everything in the past is already past. From now on, I will walk the road ahead in a relaxed way, in a happy way. My steps are like time that never stops. Next year, we will meet again.

This problem background has nothing to do with luanmenglei. Given $n, k, p$, find how many ordered $p$-tuples $(a_1, a_2, \cdots, a_p)$ satisfy: - $\forall i \in [1, p]$, $a_i \in [1, n]$. - $\forall i \in [1, p)$, $\operatorname{popcount}(a_i \oplus a_{i+1}) = k$. - $\forall i, j \in [1, p], i \neq j$, $a_i \neq a_j$. Output the answer modulo $998244353$. --- - $\operatorname{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$. - $\oplus$ denotes the bitwise XOR operation. - Two ordered $p$-tuples $(a_1, a_2, \dots, a_p)$ and $(b_1, b_2, \dots, b_p)$ are different if and only if there exists $i \in [1, p]$ such that $a_i \neq b_i$.

One line with three positive integers $n, k, p$.

One line with one integer, representing the answer.

For all testdata, it is guaranteed that $1 \leq n \leq 1000$, $1 \leq k \leq \lfloor \log_2 n \rfloor$, and $1 \leq p \leq 5$. The specific limits for each test point are shown in the table below: | Test Point ID | $n \leq$ | $p =$ | | :-: | :-: | :-: | | $1$ | $1000$ | $1$ | | $2 \sim 3$ | $1000$ | $2$ | | $4 \sim 5$ | $300$ | $3$ | | $6 \sim 12$ | $1000$ | $3$ | | $13 \sim 15$ | $1000$ | $4$ | | $16 \sim 21$ | $300$ | $5$ | | $22 \sim 25$ | $1000$ | $5$ | Translated by ChatGPT 5