No.2747 Permutation Adjacent Sum
問題文最終更新日: 2024-04-19 01:07:07
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。