102787: [AtCoder]ABC278 Ex - make 1
Description
Score : $600$ points
Problem Statement
A sequence $S$ of non-negative integers is said to be a good sequence if:
- there exists a non-empty (not necessarily contiguous) subsequence $T$ of $S$ such that the bitwise XOR of all elements in $T$ is $1$.
There are an empty sequence $A$, and $2^B$ cards with each of the integers between $0$ and $2^B-1$ written on them.
You repeat the following operation until $A$ becomes a good sequence:
- You freely choose a card and append the integer written on it to the tail of $A$. Then, you eat the card. (Once eaten, the card cannot be chosen anymore.)
How many sequences of length $N$ can be the final $A$ after the operations? Find the count modulo $998244353$.
What is bitwise XOR?
The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq B \leq 10^7$
- $N \leq 2^B$
- $N$ and $B$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $B$
Output
Print the answer.
Sample Input 1
2 2
Sample Output 1
5
The following five sequences of length $2$ can be the final $A$ after the operations.
- $(0, 1)$
- $(2, 1)$
- $(2, 3)$
- $(3, 1)$
- $(3, 2)$
Sample Input 2
2022 1119
Sample Output 2
293184537
Sample Input 3
200000 10000000
Sample Output 3
383948354
Input
题意翻译
一个非负整数序列 $S$ 是好的，当且仅当 $S$ 存在一个非空子序列 $T$，满足 $T$ 中所有元素的异或和为 $1$。 有一个初始为空的序列 $A$，以及 $2^m$ 张写着数字的卡片；卡片上的数字取遍 $[0, 2^m)$ 中的整数。你可以自由选择一张卡片，将这张卡片上的数字放在 $A$ 序列的末尾，并删除这张卡片，以后不能再选择它。你会一直进行这个操作，当 $A$ 成为好的序列后停止。 给定 $n, m$，求停止操作时长度为 $n$ 的不同 $A$ 序列数。答案对 $998244353$ 取模。 $1\le n\le 2\times 10^5, \ 1\le m \le 10^7,\ n\le 2^m$。Output
问题描述
如果一个非负整数序列$S$满足以下条件，则称其为一个 好序列：
- 存在一个非空（不一定连续）的子序列$T$，其中$T$中所有元素的按位异或值为1。
有一个空序列$A$，以及$2^B$张卡片，每张卡片上都写有0到$2^B-1$之间的整数。
当$A$成为一个好序列之前，你可以重复执行以下操作：
- 自由选择一张卡片，并将其上的整数添加到$A$的末尾。 然后吃掉这张卡片。 （一旦吃掉，这张卡片就无法再被选择了。）
执行操作后，最终的$A$有多少种可能的长度为$N$的序列？ 求出答案对$998244353$取模。
什么是按位异或？
非负整数$A$和$B$的按位异或$\mathrm{XOR}$，表示为$A \oplus B$，定义如下。- 当$A \oplus B$用二进制表示时，第$k$位最低位（$k \geq 0$）为1，如果$A$和$B$的第$k$位最低位中只有一个为1，否则为0。
限制条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq B \leq 10^7$
- $N \leq 2^B$
- $N$和$B$都是整数。
输入
输入通过标准输入以以下格式给出：
$N$ $B$
输出
打印答案。
样例输入1
2 2
样例输出1
5
以下五种长度为$2$的序列可能是执行操作后最终的$A$。
- $(0, 1)$
- $(2, 1)$
- $(2, 3)$
- $(3, 1)$
- $(3, 2)$
样例输入2
2022 1119
样例输出2
293184537
样例输入3
200000 10000000
样例输出3
383948354