「FAOI-R5」波特检测

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

小 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 0

2

2 1

4

3 1

499122184

5 2

655097885

10 3

972670600

114 514

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$。