分数: 5 点
问题陈述
给你一个字符串 S 长度 2^N 由字符组成 1, 2, \dots, 9.
对于每个非负整数 n 这样 0 \leq n \leq 2^N - 1,定义 f(n) 如下:
- 列出所有非负整数 i 这样 n \ \mathrm{OR} \ i = n,并按升序对它们进行排序。让他们成为 i_1, i_2, \dots, i_k。在这里, \mathrm{OR} 表示按位或运算。
- 让 T 是通过取 (i_1+1)-th, (i_2+1)-th, \dots, (i_k+1)第一个字符 S 按此顺序。
- 解释 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)
约束
- 1 \leq N \leq 22
- S 是一个长度为的字符串 2^N 组成
1,2, \dots,9
输入
输入由标准输入给出,格式如下:
N S
输出
打印 \displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right).
示例输入 1
2 1234
示例输出 1
1262
对于所有人 n 这样 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.
示例输入 2
4 6415986517946482
示例输出 2
790534415