AT_ttpc2023_g Cola

Alice 喜欢一个长度为 $N$ 的排列 $P=(P_1, P_2, \dots, P_N)$，其中 $P$ 是 $1,2,\dots,N$ 的一个排列。Bob 知道如果能猜中 Alice 喜欢的排列 $P$，就能从 Alice 那里得到一瓶可乐。为此，Bob 决定通过向 Alice 提问的方式来猜测 $P$。 Bob 最多可以进行 $M$ 次如下的提问： - 选择一个 $1,2,\dots,N$ 的排列 $Q=(Q_1, Q_2, \dots, Q_N)$，询问 Alice 她喜欢的排列是不是 $Q$。 其中 $M \leq N$。 Alice 对于 Bob 的每一次提问，会做出以下反应： - 若 $P=Q$，Alice 就会把可乐给 Bob。 - 若 $P \neq Q$，Alice 会告诉 Bob 所有满足 $P_i \neq Q_i$ 的 $i$ 中最小的一个 $i$。 例如，$P=(4,3,2,1)$，Bob 若用 $Q=(4,3,1,2)$ 提问，Alice 会告诉 Bob：“存在 $P_i \neq Q_i$ 的 $i$，其中最小的是 $i=3$”。 **请注意，即使在第 $M$ 次提问后确定了 $P$，Bob 也无法获得可乐。** 一开始，Bob 对 $P$ 没有任何信息。请计算当 Bob 最大化自己获得可乐的概率时，这个最大概率是多少。答案需对 $998244353$ 取模输出。 概率的 $998244353$ 取模的定义 本题中的概率总能表示为一个有理数。并且，在本题条件下，用最简分数 $\frac{y}{x}$ 表示答案时，$x$ 保证不被 $998244353$ 整除。这时，存在唯一的整数 $z$ 满足 $0\leq z

输入从标准输入中读入，格式如下： > $N\ M$

输出答案。

## 部分分 - 对于满足额外约束 $M \leq 10^{5}$ 的数据集，若答对则可获得 $70$ 分。 ## 样例解释 1 对于只进行 $1$ 次提问，可能的 $P$ 有 $2$ 个，因此有 $\frac{1}{2}$ 的概率能获得可乐。 **注意，即使第 $1$ 次没猜中，确定了 $P$ 也不能得到可乐。** ## 样例解释 2 第一次提问必然能获得可乐。 # 数据范围 - $1 \leq M \leq N \leq 10^{7}$ - 所有输入均为整数。 由 ChatGPT 5 翻译