問題一覧 > 通常問題

No.2406 Difference of Coordinate Squared

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru
3 ProblemId : 9822 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-03 22:04:20

問題文

ルエラちゃんはそれぞれ 1/41/4 の確率で 1,2,3,41,2,3,4 が出るサイコロをもっています。

ルエラちゃんは xyxy-平面の原点 (0,0)(0,0) にいて、サイコロの出た目に合わせて以下のように移動する方向を決めます。

  • 11 が出た場合、 xx 座標を 11 増やす。
  • 22 が出た場合、 xx 座標を 11 減らす。
  • 33 が出た場合、 yy 座標を 11 増やす。
  • 44 が出た場合、 yy 座標を 11 減らす。

NN 回サイコロを振ってたどり着いた点の座標を (X,Y)(X,Y) とします。 X2−Y2=MX^2-Y^2=M となる確率を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で求めてください。

「確率を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で求める」とは

求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 22 つの整数 P,QP,Q を用いて P/QP/Q と表したとき、 R×Q≡P ( ⁣ ⁣ ⁣ ⁣mod  998244353)R\times Q\equiv P\ (\!\!\!\!\mod{998244353}) かつ 0≤R<9982443530\leq R\lt 998244353 を満たす整数 RR がただ一つ存在することが証明できます。この RR を求めてください。

入力

N MN\ M

  • 入力は全て整数
  • 1≤N≤1061\leq N\leq 10^6
  • −1012≤M≤1012-10^{12}\leq M\leq 10^{12}

出力

確率を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で出力し、最後に改行してください。

サンプル

サンプル1
入力
5 3
出力
803274753

例えば 55 回サイコロを振って (2,1)(2,1) にたどりつく確率は 25/51225/512 であり、 22−12=32^2-1^2=3 を満たします。 条件を満たす他の座標 (X,Y)(X,Y) についても考えることで、求める確率が 25/12825/128 であることがわかります。

確率は  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で出力してください。

サンプル2
入力
1000000 -1000000000000
出力
874415606

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。