P11571 "chaynOI R1 T4" Orange-Red Fish


Given $r, m, s$, ask how many pairs of positive integers $(fi, sh)$ satisfy: + $0 \le fi \le sh \le r$. + $\operatorname{popcount}(fi \oplus sh) = m$. + $\operatorname{popcount}(fi + sh) = s$. Here, $\operatorname{popcount}(x)$ denotes the number of $1$'s in the binary representation of $x$, and $\oplus$ denotes the XOR operation. For convenience, $r$ is given in binary. It is guaranteed that none of the given numbers has leading $0$. Output the answer modulo $998244353$.

One line with three integers $r, m, s$.

One line with one integer, the answer modulo $998244353$.

### Sample Explanation: All numbers below are in decimal. When $r = 7$, there are six pairs: $(1,5), (2,3), (3,7), (4,5), (4,6), (5,7)$. ### Constraints: Let $n$ be the length of the given $r$. For $100\%$ of the data, $1 \le n, m, s \le 200$. **This problem uses bundled testdata.** - Subtask 1 (15 pts): $n \le 12$. - Subtask 2 (25 pts): $m, s \le 30$. - Subtask 3 (25 pts): $r = 2^n - 1$. - Subtask 4 (35 pts): no special constraints. Translated by ChatGPT 5