問題一覧 > 通常問題

No.2747 Permutation Adjacent Sum

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : tassei903 / テスター : kenken714 ponjuice
お気に入りにしたユーザー ProblemId : 10830 / 自分の提出
問題文最終更新日: 2024-04-19 01:07:07
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. Back to the original
CPCTF 2024 : PPC (順位表) の他の問題:

Problem Statement

You are given integers $N$ and $K$.

For a permutation $P$ of length $N$, define $f(P) = \sum_{i=1}^{N-1} |P_i-P_{i+1}|^K$.

Compute $f(P)$ for each of the $N!$ permutations of $(1, 2, \dots, N)$, and find the sum of these values modulo $998244353$.

Constraints

  • All input values are integers.
  • $2 \le N \le 10^9$
  • $1 \le K \le 10^6$

Input

The input is given from Standard Input in the following format.

$N$ $K$

Output

Print the answer.

Sample

Sample 1
Input
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$

Therefore, the answer is $2+3+3+3+3+2=16$.

Output
16
Sample 2
Input
100 23
Output
896913048

Print the remainder when divided by $998244353$.

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