P7322 "PMOI-4" Permutation Transformation

Given a constant $k$. For a **permutation** $a$ of length $n$, define $$f(a)=\{\max_{1 \le i \le k} \{a_i\},\max_{2 \le i \le k+1} \{a_i\},\cdots,\max_{n-k+1 \le i \le n} \{a_i\}\}$$ For a **sequence** $a$ of length $n$, define its weight $w(a)$ as the number of distinct values in $a$. Now, $\text{ducati}$ wants to know, for all permutations $p$ of length $n$, the sum of $w(f(p))$.

One line contains two positive integers $n, k$.

Output one integer in one line, representing the answer. Since the answer may be very large, you need to take it modulo $998244353$.

[Sample Explanation] - $p=\{1,2,3\}$, $f(p)=\{2,3\}$, so $w(f(p))=2$. - $p=\{1,3,2\}$, $f(p)=\{3,3\}$, so $w(f(p))=1$. - $p=\{2,1,3\}$, $f(p)=\{2,3\}$, so $w(f(p))=2$. - $p=\{2,3,1\}$, $f(p)=\{3,3\}$, so $w(f(p))=1$. - $p=\{3,1,2\}$, $f(p)=\{3,2\}$, so $w(f(p))=2$. - $p=\{3,2,1\}$, $f(p)=\{3,2\}$, so $w(f(p))=2$. The answer is $2+1+2+1+2+2=10$. [Constraints] **This problem uses bundled testdata**. - Subtask 1 (10pts): $n \le 8$. - Subtask 2 (10pts): $n \le 11$. - Subtask 3 (30pts): $n \le 100$. - Subtask 4 (20pts): $n \le 400$. - Subtask 5 (20pts): $n \le 4000$. - Subtask 6 (10pts): no special constraints. For $100\%$ of the data, $1 \le k \le n \le 5 \times 10^5$. [Notes] 1. $p$ is a permutation of length $n$ if and only if every integer in $[1,n]$ appears in $p$ **exactly once**. For example, $\{1,5,3,2,4\}$ and $\{4,2,1,3\}$ are permutations of length $5$ and $4$, respectively, while $\{1,2,2\}$ is not a permutation of length $3$, $\{5,4,3,2,1\}$ is not a permutation of length $6$, and $\{1.5,3,1\}$ is not a permutation of length $3$. 2. This problem is not difficult. Translated by ChatGPT 5