Array Beauty
Contest: Codeforces Round 572 (Div. 1)
Difficulty rating: 2500
Tags: dp

Let's call beauty of an array $$$b_1, b_2, \ldots, b_n$$$ ($$$n > 1$$$)  — $$$\min\limits_{1 \leq i < j \leq n} |b_i - b_j|$$$.

You're given an array $$$a_1, a_2, \ldots a_n$$$ and a number $$$k$$$. Calculate the sum of beauty over all subsequences of the array of length exactly $$$k$$$. As this number can be very large, output it modulo $$$998244353$$$.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

Input format:
The first line contains integers $$$n, k$$$ ($$$2 \le k \le n \le 1000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^5$$$).

Output format:
Output one integer — the sum of beauty over all subsequences of the array of length exactly $$$k$$$. As this number can be very large, output it modulo $$$998244353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$4$$$ subsequences of length $$$3$$$ — $$$[1, 7, 3]$$$, $$$[1, 3, 5]$$$, $$$[7, 3, 5]$$$, $$$[1, 7, 5]$$$, each of which has beauty $$$2$$$, so answer is $$$8$$$.

In the second example, there is only one subsequence of length $$$5$$$ — the whole array, which has the beauty equal to $$$|10-1| = 9$$$.

Example input:
4 3
1 7 3 5

Example output:
8

Example input:
5 5
1 10 100 1000 10000

Example output:
9

Editorial:
First of all, let's learn how to solve the following subtask:
For given $$$x$$$ how many subsequences of length $$$k$$$ have beauty at least $$$x$$$? If we know that the answer for $$$x$$$ is $$$p_x$$$, than the answer for original task is $$$p_1 + p_2 + \ldots + p_{max(a)}$$$, where $$$max(a)$$$ is maximum in array $$$a$$$. Let's solve subtask.
Suppose, that array is sorted. We should count subsequence $$$p_1 < p_2, \ldots < p_k$$$, iff:
$$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$.
We will solve this task using dp. The slow solution is:
$$$dp[last][cnt]$$$ — number of subsequences of length $$$cnt$$$, which end in $$$a_{last}$$$. There are transitions from state with $$$last' < last, cnt' = cnt - 1$$$, such that $$$a_{last} \ge a_{last'} + x$$$. To optimize it we need to note, that suitable $$$last'$$$ form some prefix of the array. If we know needed prefixes and prefix sums from the previous layer of dp, then we can make transitions in constant time. We can find needed prefixes using two pointers(because it's obvious, that length of prefixes doesn't decrease). So, we can solve subtask in $$$O(nk)$$$ time.
And, using solution to subtask, we can solve inital task in $$$O(max(a)nk)$$$. And here comes magic:
If $$$x > \frac{max(a)}{k - 1}$$$, than $$$p_x = 0$$$. Indeed, если $$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$, than:
$$$a_n \ge a_{p_k} \ge a_{p_{k-1}} + x \ge a_{p_{k-2}} + 2x \ldots \ge a_{p_1} + (k - 1)x \ge (k - 1)x$$$. It follows: $$$(k - 1)x \le a_n \Leftrightarrow x \le \frac{a_n}{k - 1}$$$.
So we can run our dp only for $$$x \le \frac{max(a)}{k - 1}$$$. In total our solution works in $$$O(\frac{max(a)}{k - 1}nk) = O(max(a)n)$$$ time, because $$$\frac{k}{k - 1} \le 2$$$.
$$$\textbf{Challenge}$$$
How fast you can solve the task if you need to print answer for all $$$2 \le k \le n$$$?
// code