P11658 "FAOI-R5" Bot Detection.

Verifying whether you are a real person. This may take a few seconds.

Little H is a bot. He has a built-in sequence $\{A_n\}$ and a binary string $H$ of length $n$. If you ask him about an interval $[l,r]$, he can give a **set** $g(l,r)$: - Define a sequence $\{B_n\}$. For $i=1,2,\ldots,n$, do the following: - If $H_i=\tt{0}$, then $B_i=A_i$ (i.e., Little H cannot change the value of $A_i$). - If $H_i=\tt{1}$, he may choose any non-negative integer $v$ and set $B_i=v$ (i.e., Little H may change the value of $A_i$ arbitrarily, **and the modified value does not have to be within $\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}\}$. Meowzai Milk needs to perform several tests on Little H. In each test, two intervals $[l,r]$ and $[L,R]$ are chosen such that $r\le L$, and Meowzai Milk asks Little H and obtains $g(l,r)$ and $g(L,R)$. If $g(l,r)\cap g(L,R)\neq\varnothing$, then the test fails, and Little H’s bot identity will be exposed. If Little H has a strategy to answer all possible queries such that no test ever fails (that is, for any intervals $[l,r]$ and $[L,R]$ satisfying $r\le L$, the test will not fail), then we call the binary string $H$ "usable". Given $n,k$, each term of the sequence $\{A_n\}$ is chosen independently and uniformly at random from $[0,2^k-1]$. You need to compute the expected number of "usable" binary strings $H$. Output the answer modulo $998244353$.

A single line with two non-negative integers $n,k$, representing the length of the sequence and the size of the value range.

A single line with one non-negative integer, representing the expected number of "usable" binary strings $H$ modulo $998244353$. If you do not know how to take a rational number modulo: - Let $M=998244353$. It can be proven that the answer can be written as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are positive integers and $q\not\equiv 0\pmod M$. You only need to output a non-negative integer $x\in[0,M)$ such that $x\cdot q\equiv p\pmod M$. - If you do not know how to find such an $x$, you may refer to P2613.

### Explanation for Sample 1 The only possible case is $A=[0]$. Then both $H=\tt 0$ and $H=\tt 1$ are "usable", so the answer is $2$. ### Explanation for Sample 2 There are $4$ possible cases: - $A=[0,0]$. - $A=[0,1]$. - $A=[1,0]$. - $A=[1,1]$. Without any modification, all of them can pass the test (the corresponding answers are all $2^2=4$), so the answer is $2^2=4$. ### Explanation for Sample 3 There are $8$ possible cases: - $A=[0,0,0]$, the number of valid $H$ is $7$. - $A=[0,0,1]$, the number of valid $H$ is $8$. - $A=[0,1,0]$, the number of valid $H$ is $7$. - $A=[0,1,1]$, the number of valid $H$ is $8$. - $A=[1,0,0]$, the number of valid $H$ is $8$. - $A=[1,0,1]$, the number of valid $H$ is $7$. - $A=[1,1,0]$, the number of valid $H$ is $8$. - $A=[1,1,1]$, the number of valid $H$ is $7$. When $A=[0,1,0]$, $H=\tt{000}$ is not "usable". When querying $[1,2]$ and $[2,3]$: - Little H can only keep $A$ unchanged each time. - When querying $[1,2]$, $g(1,2)=\{1\}$. - When querying $[2,3]$, $g(2,3)=\{1\}$. - $g(1,2)\cap g(2,3)=\{1\}$, so the test fails. When $A=[1,1,1]$, $H=\tt{010}$ is "usable". When querying $[1,2]$ and $[2,3]$: - Little H may modify the values of $A$ arbitrarily, **and the modified values may be different for each query**. - When querying $[1,2]$, Little H sets $B=[1,2,1]$, so $g(1,2)=\{3\}$. - When querying $[2,3]$, Little H sets $B=[1,1,1]$, so $g(2,3)=\{0\}$. - $g(1,2)\cap g(2,3)=\varnothing$, so the test succeeds. Therefore, the answer is $(7\times 4+8\times 4)\times\dfrac{1}{8}=\dfrac{15}{2}$. Note that $2\times 499122184\equiv 15\pmod{998244353}$, so the answer is $499122184$. ### Explanation for Sample 4 The answer is $\dfrac{907}{32}\equiv655097885\pmod{998244353}$. ### Constraints and Notes **This problem uses bundled subtasks.** - Subtask 1 (10 pts): $n\leq2$. - Subtask 2 (10 pts): $n\leq 6$ and $k\leq 2$. - Subtask 3 (10 pts): $n\leq 50$ and $k\leq6$. - Subtask 4 (10 pts): $n\leq 500$ and $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): no special restrictions. For all testdata, $1\leq n\leq 10^6$ and $0\leq k\leq 10^9$. Translated by ChatGPT 5