atcoder#ABC278H. [ABC278Ex] make 1

[ABC278Ex] make 1

题目描述

次の条件を満たす非負整数列 S S 良い数列 と呼びます。

  • S S の(連続とは限らない)非空な部分列 T T であって、T T のすべての要素のビットごとの xor が 1 1 であるようなものが存在する。

空の数列 A A 、および 0 0 以上 2B 2^B 未満の整数が 1 つずつ書かれた 2B 2^B 枚のカードがあります。
あなたは次の操作を A A が良い数列になるまで繰り返します。

  • カードを 1 枚自由に選び、カードに書かれている数を A A の末尾に追加する。そして選んだカードを食べる。(食べたカードはその後選ぶことはできない)

操作後の A A としてあり得る数列のうち長さが N N であるものは何種類ありますか? 答えを mod 998244353 \text{mod\ }998244353 で出力してください。

ビットごとの xor とは? 非負整数 A, B A,\ B のビット単位 xor 、A  B A\ \oplus\ B は、以下のように定義されます。 - A  B A\ \oplus\ B を二進表記した際の 2k 2^k (k  0 k\ \geq\ 0 ) の位の数は、A, B A,\ B を二進表記した際の 2k 2^k の位の数のうち一方のみが 1 1 であれば 1 1 、そうでなければ 0 0 である。

例えば、3  5 = 6 3\ \oplus\ 5\ =\ 6 となります (二進表記すると: 011  101 = 110 011\ \oplus\ 101\ =\ 110 )。

输入格式

入力は以下の形式で標準入力から与えられる。

N N B B

输出格式

答えを出力せよ。

题目大意

一个非负整数序列 SS 是好的,当且仅当 SS 存在一个非空子序列 TT,满足 TT 中所有元素的异或和为 11

有一个初始为空的序列 AA,以及 2m2^m 张写着数字的卡片;卡片上的数字取遍 [0,2m)[0, 2^m) 中的整数。你可以自由选择一张卡片,将这张卡片上的数字放在 AA 序列的末尾,并删除这张卡片,以后不能再选择它。你会一直进行这个操作,当 AA 成为好的序列后停止。

给定 n,mn, m,求停止操作时长度为 nn 的不同 AA 序列数。答案对 998244353998244353 取模。

$1\le n\le 2\times 10^5, \ 1\le m \le 10^7,\ n\le 2^m$。

2 2
5
2022 1119
293184537
200000 10000000
383948354

提示

制約

  • 1  N  2 × 105 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • 1  B  107 1\ \leq\ B\ \leq\ 10^7
  • N  2B N\ \leq\ 2^B
  • N, B N,\ B は整数

Sample Explanation 1

操作後の A A としてあり得る数列のうち長さが 2 2 であるものは次の 5 5 種類です。 - (0, 1) (0,\ 1) - (2, 1) (2,\ 1) - (2, 3) (2,\ 3) - (3, 1) (3,\ 1) - (3, 2) (3,\ 2)