← 返回题目列表

AtCoder · ndpc2026_m

M. 数字

中文机器翻译题面 查看原题

分数: 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