分数: 5 点
问题陈述
有一个简单的无向图 2^N+1 顶点和 2^N 边,其中顶点编号 1, 2, \dots, 2^N+1.
的 i第一条边连接顶点 i 和顶点 i+1.
你在顶点上放置了一块 1。然后你完全重复下面的操作 T 次:
- 设当前顶点为 v。选择一个相邻的顶点 v 随机均匀,并将棋子移动到该顶点。
之后 T 操作,计算该块位于顶点的概率 X,模数 998244353.
概率模是什么意思 998244353 是什么意思?
可以证明概率总是有理数。 在这个问题的约束下,如果概率写成 \tfrac{P}{Q} 与互质整数 P 和 Q, 那么存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R < 998244353。 你被要求计算这个 R.约束
- 1 \leq N \leq 20
- 1 \leq T \leq 10^{18}
- 1 \leq X \leq 2^N+1
- 所有输入值均为整数
部分分数
该问题有部分评分:
- 如果您使用以下方法求解所有数据集 N \leq 14,您将获得 3 点。
输入
输入由标准输入给出,格式如下:
N T X
输出
打印答案。
示例输入 1
2 3 2
示例输出 1
249561089
可能的行动及其概率是:
- 移动 1 \to 2 \to 3 \to 2 有概率 \tfrac{1}{4}.
- 移动 1 \to 2 \to 1 \to 2 有概率 \tfrac{1}{2}.
因此,答案是 \tfrac{3}{4}.
示例输入 2
10 12345 678
示例输出 2
530802129