問題一覧 > 通常問題

No.2747 Permutation Adjacent Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : tassei903tassei903 / テスター : kenken714kenken714 ponjuiceponjuice
1 ProblemId : 10830 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-19 01:07:07

問題文

整数 $N$, $K$ が与えられます。

長さ $N$ の順列 $P$ に対して、 $f(P) = \sum_{i=1}^{N-1} |P_i-P_{i+1}|^K$ と定めます。

$(1, 2, \dots, N)$ の順列 $N!$ 通りについて $f(P)$ を計算し、その総和を $998244353$ で割ったあまりを求めてください。

制約

  • 入力はすべて整数
  • $2 \le N \le 10^9$
  • $1 \le K \le 10^6$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

出力

答えを出力せよ。

サンプル

サンプル1
入力
3 1
  • $f((1, 2, 3)) = |1 - 2| + |2 - 3| = 2$
  • $f((1, 3, 2)) = |1 - 3| + |3 - 2| = 3$
  • $f((2, 1, 3)) = |2 - 1| + |1 - 3| = 3$
  • $f((2, 3, 1)) = |2 - 3| + |3 - 1| = 3$
  • $f((3, 1, 2)) = |3 - 1| + |1 - 2| = 3$
  • $f((3, 2, 1)) = |3 - 2| + |2 - 1| = 2$

以上から、答えは $2+3+3+3+3+2=16$ です。

出力
16
サンプル2
入力
100 23
出力
896913048

$998244353$ で割ったあまりを出力してください。

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