PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Combinatorics
PROBLEM:
For an array A, define f(A) to be the maximum value of A_i + A_j across all i \lt j such that A_i \gt A_j.
If no such pair exists, f(A) = 0 instead.
Given N, compute the sum of f(P) across all permutations P of [1, N].
EXPLANATION:
A permutation has distinct elements in [1, N].
Observe that the answer for a fixed permutation cannot exceed 2N-1, since at best we can choose N and N-1.
Thus, to sum up the answer across all permutations, we can instead try to compute the number of permutations for which the answer is equal to K, for each 0 \le K \le 2N-1.
If this value is denoted x_K, the answer is simply
Now, it’s somewhat hard to count the number of permutations with answer exactly equal to K.
So, we will instead relax the condition slightly and try to count permutations whose answer is at most K.
If this value is denoted f(N, K), then observe that we have x_K = f(N, K) - f(N, K-1).
Thus, we only need to compute all the f(N, K) values and we get all the x_K from them for free.
Let’s now look at computing f(N, K) for a fixed value of K.
We’ll distinguish two cases: N \ge K and N \lt K.
Case 1: N \lt K
Let d = K-N denote the difference between them.
We want to count permutations such that there don’t exist two elements x and y satisfying:
- x \lt y,
- x appears after y, and
- x+y \gt K
Now, note that any element of the permutation that’s \le d can never be part of such a pair anyway; since the maximum sum it can attain is bounded above by d+N = K.
So, the positions and order of the elements 1,2, \ldots, d just don’t matter at all.
We can thus freely place these elements and then forget about them.
There are \binom{N}{d} ways to choose their positions, and then d! ways to arrange them among their positions.
We are now left with the elements d+1, \ldots, N that need to be placed at the remaining N-d positions.
Let’s subtract d from each of these elements and treat them as 1, 2, \ldots, N-d.
Doing this also subtracts 2d from the sum of any pair.
So, when working with 1, 2, \ldots, N-d the maximum allowed pair sum is K - 2d.
However, K = N+d, so K-2d = N-d.
Thus, we have the elements 1, 2, \ldots, N-d and we want to count their arrangements such that no inversion pair has a sum exceeding N-d.
This is, by definition, f(N-d, N-d).
So, we have
where d = K-N.
Note that the computation of f(N-d, N-d) isn’t yet known to us; so we look at the second case.
Case 2: N \ge K
Observe that in this case, the last element of the permutation is forced to be N itself; since otherwise N with any element after it would result in an inversion with larger sum than N, but K \le N.
This leaves the elements 1, 2, 3, \ldots, N-1 at the remaining N-1 positions.
If K \le N-1, the exact same argument tells us that the second-last element is forced to be N-1.
In fact, simply generalizing this, all the elements K, K+1, \ldots, N must appear at the end of the permutation in ascending order, since involving any of them in an inversion is bad.
This leaves the elements 1, 2, \ldots, K-1 to fill the first K-1 positions, with inversions not exceeding K in sum.
By definition, the number of valid arrangements now equals f(K-1, K).
However, let’s look a bit closer at f(K-1, K).
Looking back at the recurrence derived in case 1, we see that we have d = 1 and hence
But we also directly had f(N, K) = f(K-1, K).
So, we have
This applies to any N \ge K, and so in particular it applies to N = K, thus giving us
This is a useful recurrence because it allows us to precompute all the f(x, x) values for 1 \le x \le N in linear time.
Once all the f(x, x) values are known, any f(N, K) can be computed in constant time via
for K \gt N and
for K \le N.
As we saw at the start, this is enough to compute the final answer!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 998244353
fac = [1] + list(range(1, 200005))
for i in range(1, 200005): fac[i] = (i * fac[i-1]) % mod
def C(n, r):
if r < 0 or r > n: return 0
return fac[n] * pow(fac[r] * fac[n-r], mod-2, mod) % mod
for _ in range(int(input())):
n = int(input())
f = [1]*(n+1)
for i in range(2, n+1):
f[i] = (i-1) * f[i-2] % mod
ans, prv = 0, 1
for k in range(1, 2*n):
cur = 0
if k > n:
d = k - n
cur = C(n, d) * fac[d] * f[n-d] % mod
else:
cur = f[k]
ans += (cur - prv) * k
prv = cur
print(ans % mod)