AT_abc278_h [ABC278Ex] make 1

题目描述

我们称满足下列条件的非负整数序列 $S$ 为好序列：

• 存在 $S$ 的一个（不一定连续的）非空子序列 $T$，使得 $T$ 的所有元素的按位异或结果为 $1$。

现有一个空序列 $A$，以及 $2^B$ 张卡片，每张卡片上写有一个 $0$ 到 $2^B-1$ 之间的整数，且每个数各出现一次。
你可以重复以下操作，直到 $A$ 变成好序列为止：

• 任意选择一张卡片，将卡片上的数添加到 $A$ 的末尾，并吃掉这张卡片（被吃掉的卡片不能再选）。

在所有可能的操作后，长度为 $N$ 的 $A$ 有多少种不同的取法？请输出答案对 $998244353$ 取模后的结果。

什么是按位异或？非负整数 $A,\ B$ 的按位异或 $A\oplus B$ 定义如下：

• $A\oplus B$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $A$ 和 $B$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3\oplus 5 = 6$（二进制表示为：$011\oplus 101 = 110$）。

输入格式

输入通过标准输入给出，格式如下：

$N$ $B$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 2

输出 #1

5

输入输出样例 #2

输入 #2

2022 1119

输出 #2

293184537

输入输出样例 #3

输入 #3

200000 10000000

输出 #3

383948354

说明/提示

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq B \leq 10^7$
• $N \leq 2^B$
• $N,\ B$ 为整数

样例解释 1

所有可能的长度为 $2$ 的 $A$ 如下，共有 $5$ 种：

• $(0, 1)$
• $(2, 1)$
• $(2, 3)$
• $(3, 1)$
• $(3, 2)$

由 ChatGPT 4.1 翻译