/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 5 点
問題文
頂点に 1, 2, \dots, 2^N+1 の番号がついた 2^N+1 頂点 2^N 辺の単純無向グラフがあります。i 番目の辺は頂点 i と頂点 i+1 を結んでいます。
あなたは頂点 1 に駒を置きます。その後、以下の操作をちょうど T 回繰り返します。
- 現在駒がある頂点を v とする。v に隣接する頂点の中から 1 個の頂点を一様ランダムに選び、選んだ頂点に駒を移動させる。
T 回の操作を終了した時点で頂点 X に駒がある確率を \text{mod }998244353 で求めてください。
確率 \text{mod }998244353 とは
求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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 と移動する確率が \frac{1}{4}、
- 頂点 1 \to 頂点 2 \to 頂点 1 \to 頂点 2 と移動する確率が \frac{1}{2}
となります。よって答えは \frac{3}{4} です。
入力例 2
10 12345 678
出力例 2
530802129
Score: 5 points
Problem Statement
There is a simple undirected graph with 2^N+1 vertices and 2^N edges, where the vertices are numbered 1, 2, \dots, 2^N+1.
The i-th edge connects vertex i and vertex i+1.
You place a piece on vertex 1. Then you repeat the following operation exactly T times:
- Let the current vertex be v. Choose one adjacent vertex of v uniformly at random, and move the piece to that vertex.
After T operations, compute the probability that the piece is on vertex X, modulo 998244353.
What does probability modulo 998244353 mean?
It can be proven that the probability is always a rational number. Under the constraints of this problem, if the probability is written as \tfrac{P}{Q} with coprime integers P and Q, then there exists a unique integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. You are asked to compute this R.Constraints
- 1 \leq N \leq 20
- 1 \leq T \leq 10^{18}
- 1 \leq X \leq 2^N+1
- All input values are integers
Partial Score
This problem has partial scoring:
- If you solve all datasets with N \leq 14, you will earn 3 points.
Input
The input is given from standard input in the following format:
N T X
Output
Print the answer.
Sample Input 1
2 3 2
Sample Output 1
249561089
The possible moves and their probabilities are:
- Move 1 \to 2 \to 3 \to 2 with probability \tfrac{1}{4}.
- Move 1 \to 2 \to 1 \to 2 with probability \tfrac{1}{2}.
Thus, the answer is \tfrac{3}{4}.
Sample Input 2
10 12345 678
Sample Output 2
530802129