No.2406 Difference of Coordinate Squared
タグ : / 解いたユーザー数 54
作問者 : 👑
amentorimaru
問題文
ルエラちゃんはそれぞれ $1/4$ の確率で $1,2,3,4$ が出るサイコロをもっています。
ルエラちゃんは $xy$-平面の原点 $(0,0)$ にいて、サイコロの出た目に合わせて以下のように移動する方向を決めます。
- $1$ が出た場合、 $x$ 座標を $1$ 増やす。
- $2$ が出た場合、 $x$ 座標を $1$ 減らす。
- $3$ が出た場合、 $y$ 座標を $1$ 増やす。
- $4$ が出た場合、 $y$ 座標を $1$ 減らす。
$N$ 回サイコロを振ってたどり着いた点の座標を $(X,Y)$ とします。 $X^2-Y^2=M$ となる確率を $\!\!\!\!\mod{998244353}$ で求めてください。
「確率を $\!\!\!\!\mod{998244353}$ で求める」とは
求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P,Q$ を用いて $P/Q$ と表したとき、 $R\times Q\equiv P\ (\!\!\!\!\mod{998244353})$ かつ $0\leq R\lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。
入力
$N\ M$
- 入力は全て整数
- $1\leq N\leq 10^6$
- $-10^{12}\leq M\leq 10^{12}$
出力
確率を $\!\!\!\!\mod{998244353}$ で出力し、最後に改行してください。
サンプル
サンプル1
入力
5 3
出力
803274753
例えば $5$ 回サイコロを振って $(2,1)$ にたどりつく確率は $25/512$ であり、 $2^2-1^2=3$ を満たします。 条件を満たす他の座標 $(X,Y)$ についても考えることで、求める確率が $25/128$ であることがわかります。
確率は $\!\!\!\!\mod{998244353}$ で出力してください。
サンプル2
入力
1000000 -1000000000000
出力
874415606
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。