問題一覧 > 通常問題

No.2113 Distance Sequence 1.5

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 74
作問者 : bayashikobayashiko / テスター : kotatsugamekotatsugame noiminoimi
2 ProblemId : 8623 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-28 17:08:46

問題文

椎葉さんと因幡さんが、要素数が $2N$ で $1$ 以上 $M$ 以下の整数からなる整数列 $A=(a_1,a_2,\ldots,a_{2N})$ と 空の整数列 $B$ を用いてゲームをします。

椎葉さんが先手で、 $A$ が空になるまで交互に以下の操作を繰り返します。

  • $A$ の要素を $1$ つ選び、 $A$ から削除し、$B$ の末尾に加える。

$A$ が空になったときの $B$ の要素数は $2N$ ですが、これを $B=(b_1,b_2,\ldots,b_{2N})$ としたとき、ある整数 $j$ $(1 \leq j \leq 2N-1)$ が存在して $|b_j-b_{j+1}| \geq K$ が成立するならば後手の因幡さんの勝ちで、そうでないなら先手の椎葉さんの勝ちです。

整数列 $A$ として考えられるものは全部で $M^{2N}$ 通りありますが、そのうち両者が最適にゲームを進めたとき、先手の椎葉さんが勝つようなものは全部で何通りありますか?

答えを $998244353$ で割った余りを求めてください。

入力

$N \ M \ K$

  • $1\le N,M,K\le 10^{18}$
  • 入力はすべて整数

出力

答えを $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
2 2 1
出力
2

$A$ として考えられるものは全部で $16$ 通りありますが、そのうち先手の椎葉さんが勝つのは以下の $2$ 通りです。

  • $(1,1,1,1)$
  • $(2,2,2,2)$

サンプル2
入力
3 3 3
出力
729

$A$ として考えられるものは全部で $729$ 通りあり、その全てで椎葉さんが勝ちます。

サンプル3
入力
178096 418269 13333
出力
111203503

答えを $998244353$ で割った余りを出力することに注意してください。

サンプル4
入力
1000 1000000000000 998244853
出力
662474981

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