AT_fps_24_r ランダムウォーク

题目描述

有一个简单无向图，共有 $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$。

输入格式

输入从标准输入中获取，格式如下：

$N$ ~$T$ ~$X$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 3 2

输出 #1

249561089

输入输出样例 #2

输入 #2

10 12345 678

输出 #2

530802129

说明/提示

部分分数

本题有部分分计分：

• 若你能解出所有 $N \leq 14$ 的测试点，可以获得 $3$ 分。

样例解释 1

所有可能的移动及其概率如下：

• 移动 $1 \to 2 \to 3 \to 2$，概率为 $\tfrac{1}{4}$。
• 移动 $1 \to 2 \to 1 \to 2$，概率为 $\tfrac{1}{2}$。

因此，答案为 $\tfrac{3}{4}$。

数据范围

• $1 \leq N \leq 20$
• $1 \leq T \leq 10^{18}$
• $1 \leq X \leq 2^N+1$
• 所有输入值均为整数。

由 ChatGPT 5 翻译