No.2406 Difference of Coordinate Squared
タグ : / 解いたユーザー数 61
作問者 : 👑
amentorimaru
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
Ruera has a die that shows each of $1,2,3,4$ with probability $1/4$.
Ruera is at the origin $(0,0)$ of the $xy$-plane, and decides the direction of each move according to the number shown on the die, as follows.
- If $1$ is shown, increase the $x$ coordinate by $1$.
- If $2$ is shown, decrease the $x$ coordinate by $1$.
- If $3$ is shown, increase the $y$ coordinate by $1$.
- If $4$ is shown, decrease the $y$ coordinate by $1$.
Let $(X,Y)$ be the coordinates of the point reached after rolling the die $N$ times. Find the probability that $X^2-Y^2=M$, modulo $\!\!\!\!\mod{998244353}$.
What "find the probability $\!\!\!\!\mod{998244353}$" means
It can be proved that the desired probability is always a rational number. Moreover, under the constraints of this problem, it can be proved that when the value is expressed as $P/Q$ using $2$ coprime integers $P,Q$, there exists exactly one integer $R$ such that $R\times Q\equiv P\ (\!\!\!\!\mod{998244353})$ and $0\leq R\lt 998244353$. Find this $R$.
Input
$N\ M$
- All inputs are integers.
- $1\leq N\leq 10^6$
- $-10^{12}\leq M\leq 10^{12}$
Output
Print the probability $\!\!\!\!\mod{998244353}$, followed by a newline.
Sample
Sample 1
Input
5 3
Output
803274753
For example, the probability of reaching $(2,1)$ after rolling the die $5$ times is $25/512$, and it satisfies $2^2-1^2=3$. By also considering the other coordinates $(X,Y)$ that satisfy the condition, we find that the desired probability is $25/128$.
Print the probability $\!\!\!\!\mod{998244353}$.
Sample 2
Input
1000000 -1000000000000
Output
874415606
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。