贡献名单

想法	标程	数据	验题	题解
喵仔牛奶			紊莫	喵仔牛奶

题目背景

正在验证您是否是真人。这可能需要几秒钟时间。

题目描述

小 H 是一个 bot，他内置一个序列 $\{A_n\}$ 和一个长度为 $n$ 的 01 串 $H$。询问他一个区间 $[l,r]$，他可以给出一个集合 $g(l,r)$:

• 设置序列 $\{B_n\}$，对于 $i=1,2,\ldots,n$，执行以下操作：
  • 如果 $H_i=\tt{0}$，$B_i=A_i$（即小 H 不能修改 $A_i$ 的值）；
  • 如果 $H_i=\tt{1}$，可以任意选择一个非负整数 $v$，令 $B_i=v$（即小 H 可以任意修改 $A_i$ 的值，修改后的值可以不在 $\boldsymbol{[0,2^k-1]}$ 范围内）。
• $g(l,r)=\{B_l\operatorname{xor}B_{l+1},B_{l+1}\operatorname{xor}B_{l+2},\cdots,B_{r-1}\operatorname{xor}B_{r}\}$。

喵仔牛奶需要对小 H 进行若干次检测，每次选取 $[l,r],[L,R]$ 两个区间，满足 $r\le L$，并向小 H 询问得出 $g(l,r),g(L,R)$。若 $g(l,r)\cap g(L,R)\neq\varnothing$，则检测失败，小 H 的 bot 身份会被发现。

若小 H 存在一种策略可以回答所有可能的询问并不存在检测失败（也就是对于任意满足 $r\le L$ 区间 $[l,r],[L,R]$ 都不会检测失败），我们就称这个 01 串 $H$ 是「可用的」。

给定 $n,k$，序列 $\{A_n\}$ 的每一项都在 $[0,2^k-1]$ 中均匀随机选取。你需要求出「可用的」01 串 $H$ 的个数的期望值。答案对 $998244353$ 取模。

输入格式

一行两个非负整数 $n,k$，表示序列长度与值域大小。

输出格式

一行一个非负整数，表示「可用的」01 串 $H$ 的个数的期望值对 $998244353$ 取模后的结果。

如果你不知道如何进行有理数取模：

• 令 $M=998244353$。可以证明，答案可以被表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是正整数且 $q\not\equiv 0\pmod M$。你只需要输出一个非负整数 $x\in[0,M)$ 使得 $x\cdot q\equiv p\pmod M$。
• 如果你不知道如何找出所述的 $x$，可以参考 P2613。

样例 #1

样例输入 #1

1 0

样例输出 #1

2

样例 #2

样例输入 #2

2 1

样例输出 #2

4

样例 #3

样例输入 #3

3 1

样例输出 #3

499122184

样例 #4

样例输入 #4

5 2

样例输出 #4

655097885

样例 #5

样例输入 #5

10 3

样例输出 #5

972670600

样例 #6

样例输入 #6

114 514

样例输出 #6

802524221

提示

样例 1 解释

唯一一种可能的情况是 $A=[0]$，此时 $H=\tt 0$ 和 $H=\tt 1$ 都是「可用的」，故答案为 $2$。

样例 2 解释

有以下 $4$ 种可能的情况：

• $A=[0,0]$。
• $A=[0,1]$。
• $A=[1,0]$。
• $A=[1,1]$。

在不修改的情况下，它们都能通过检测（对应的答案均为 $2^2=4$），故答案为 $2^2=4$。

样例 3 解释

有以下 $8$ 种可能的情况：

• $A=[0,0,0]$，$H$ 的个数为 $7$。
• $A=[0,0,1]$，$H$ 的个数为 $8$。
• $A=[0,1,0]$，$H$ 的个数为 $7$。
• $A=[0,1,1]$，$H$ 的个数为 $8$。
• $A=[1,0,0]$，$H$ 的个数为 $8$。
• $A=[1,0,1]$，$H$ 的个数为 $7$。
• $A=[1,1,0]$，$H$ 的个数为 $8$。
• $A=[1,1,1]$，$H$ 的个数为 $7$。

当 $A=[0,1,0]$ 时，$H=\tt{000}$ 不是「可用的」。当询问 $[1,2],[2,3]$ 时：

• 小 H 每次只能原封不动地保留 $A$。
• 当询问 $[1,2]$ 时，$g(1,2)=\{1\}$。
• 当询问 $[2,3]$ 时，$g(2,3)=\{1\}$。
• $g(1,2)\cap g(2,3)=\{1\}$，检测失败。

当 $A=[1,1,1]$ 时，$H=\tt{010}$ 是「可用的」。当询问 $[1,2],[2,3]$ 时：

• 小 H 可以任意修改 $A$ 的值，并且每次询问时修改的值可以不一样。
• 当询问 $[1,2]$ 时，小 H 令 $B=[1,2,1]$，$g(1,2)=\{3\}$。
• 当询问 $[2,3]$ 时，小 H 令 $B=[1,1,1]$，$g(2,3)=\{0\}$。
• $g(1,2)\cap g(2,3)=\varnothing$，检测成功。

故答案为 $(7\times 4+8\times 4)\times\dfrac{1}{8}=\dfrac{15}{2}$。

注意到 $2\times 499122184\equiv 15\pmod{998244353}$，答案即为 $499122184$。

样例 4 解释

答案为 $\dfrac{907}{32}\equiv655097885\pmod{998244353}$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$n\leq2$。
• Subtask 2（10 pts）：$n\leq 6$，$k\leq 2$。
• Subtask 3（10 pts）：$n\leq 50$，$k\leq6$。
• Subtask 4（10 pts）：$n\leq 500$，$k\leq 20$。
• Subtask 5（20 pts）：$n\leq 2\times10^3$。
• Subtask 6（20 pts）：$n\leq 5\times10^4$。
• Subtask 7（20 pts）：无特殊限制。

对于所有数据，$1\leq n\leq 10^6$，$0\leq k\leq 10^9$。