← 返回题目列表

AtCoder · fps_24_r

R. 随机游走

中文机器翻译题面 查看原题

分数: 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