AT_ndpc2026_m 数字

给定一个长度为 $2^N$ 的字符串 $S$，该字符串仅由字符 `1`、`2`、$\dots$、`9` 组成。 对于每个满足 $0 \leq n \leq 2^N - 1$ 的非负整数 $n$，定义 $f(n)$ 如下： - 枚举所有非负整数 $i$ 满足 $n\,\mathrm{OR}\,i = n$，并将它们升序排列，记为 $i_1, i_2, \dots, i_k$。其中 $\mathrm{OR}$ 表示按位或运算。 - 取 $S$ 的第 $i_1+1$、$i_2+1$、$\dots$、$i_k+1$ 个字符，按顺序依次拼接得到新字符串 $T$。 - 把字符串 $T$ 作为十进制整数解释，得到数值 $X$。定义 $f(n) = X \bmod 998244353$。 请计算所有 $f(0), f(1), \dots, f(2^N-1)$ 的值，并输出下式的结果，其中 $\mathrm{XOR}$ 表示按位异或运算： $$ \displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right) $$

输入包含一行： > $N$ $S$

输出一个整数，表示 $$ \displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right) $$ 的值。

### 样例解释 1 对于所有 $0 \leq n \leq 2^N - 1$，$f(n)$ 的值如下： - 当 $n=0$ 时，$f(n)=1$ - 当 $n=1$ 时，$f(n)=12$ - 当 $n=2$ 时，$f(n)=13$ - 当 $n=3$ 时，$f(n)=1234$ 所以输出为 $(1\ \mathrm{XOR}\ 0) + (12\ \mathrm{XOR}\ 1) + (13\ \mathrm{XOR}\ 2) + (1234\ \mathrm{XOR}\ 3) = 1 + 13 + 15 + 1233 = 1262$。 ### 数据范围 - $1 \leq N \leq 22$ - $S$ 是一个长度为 $2^N$ 仅包含 `1`、`2`、$\dots$、`9` 的字符串。 由 ChatGPT 5 翻译