AT_arc139_f.[ARC139F] Many Xor Optimization Problems

PCT 君出了一道如下题目。

Xor 优化问题
给定一个长度为 $N$ 的非负整数序列 $A_1,A_2,\ldots,A_N$。你可以任选若干个 $A$ 的元素，所选元素的 $\mathrm{XOR}$ 能取得的最大值是多少？

由于这道题对 Nyaan 君来说太简单了，PCT 君将题目改成了如下形式。

多个 Xor 优化问题
长度为 $N$ 且所有元素都在 $0$ 到 $2^M-1$ 之间的整数序列共有 $2^{NM}$ 种。对于所有这些序列，分别求解 Xor 优化问题，将所有答案之和对 $998244353$ 取模，输出结果。

请你解决 多个 Xor 优化问题。

$\mathrm{XOR}$ 的定义如下：
对于非负整数 $A,B$，它们的按位 $\mathrm{XOR}$，记作 $A\oplus B$，定义为：

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

例如，$3\oplus 5=6$（二进制表示为：$011\oplus 101=110$）。
一般地，$k$ 个非负整数 $p_1,p_2,\ldots,p_k$ 的按位 $\mathrm{XOR}$ 定义为 $(\cdots((p_1\oplus p_2)\oplus p_3)\oplus\cdots\oplus p_k)$，并且可以证明其结果与顺序无关。

输入从标准输入读入，格式如下：

$N$ $M$

请输出答案。

数据范围

• $1\leq N,M\leq 250000$
• 输入均为整数。

样例解释 1

对于长度为 $2$ 且所有元素都在 $0$ 到 $1$ 之间的所有整数序列，分别求解 Xor 优化问题。

• 当 $A=(0,0)$ 时，答案为 $0$
• 当 $A=(0,1)$ 时，答案为 $1$
• 当 $A=(1,0)$ 时，答案为 $1$
• 当 $A=(1,1)$ 时，答案为 $1$
  因此，$0+1+1+1=3$，即为答案。

由 ChatGPT 4.1 翻译