INCWINDOW - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Binary exponentiation, binomial coefficients

PROBLEM:

Given N and K, count the number of arrays A of length N with elements in [1, N] such that the array B defined by B_i = \max(A_i, \ldots, A_{i+K-1}) is strictly increasing.

EXPLANATION:

We want the maximums of the length-K subarrays to be strictly increasing, from left to right.

In particular, this means we want \max(A_1, \ldots, A_K) \lt \max(A_2, \ldots, A_{K+1}) to hold.
Observe that this is possible if and only if \max(A_2, \ldots, A_{K+1}) = A_{K+1}, because if the largest element of [2, K+1] appeared at some index in [2, K], then it would be present in [1, K] as well (and so the maximum of [1, K] can’t be strictly smaller than the maximum of [2, K+1]).

Thus, we definitely need A_{K+1} to be strictly larger than all of A_1, A_2, \ldots, A_K.

The same logic applies to every following index as well: A_{K+2} needs to be strictly larger than \max(A_2, \ldots, A_{K+1}), then A_{K+3} needs to be strictly larger than \max(A_3, \ldots, A_{K+2}), and so on.
However, because A_{K+1} = \max(A_2, \ldots, A_{K+1}, this is equivalent to saying

\max(A_1, \ldots, A_K) \lt A_{K+1} \lt A_{K+2} \lt\ldots\lt A_N

That is, after fixing the first K elements, the remaining elements must be in strictly increasing order.

We can use the above characterization to count the number of valid arrays.

Let’s fix M = \max(A_1, \ldots, A_K) to be the largest element among the first K indices.
Then,

  • There are M^K ways to choose the first K elements such that they’re all \le M.
  • However, we want the maximum to be exactly M.
    So, we subtract (M-1)^K, which is the number of ways in which all these K elements are \lt M.
  • Once this is done, we need to choose A_{K+1}, \ldots, A_N.
    These must be strictly increasing, and must also all be \gt M.
    So, what we’re doing is really just choosing N-K distinct elements from the range [M+1, N] and arranging them in ascending order.
    There are \binom{N-M}{N-K} ways of doing this.

The total count is obtained by summing up across all M, and so equals

\sum_{M=1}^N \left(M^K - (M-1)^K\right) \binom{N-M}{N-K}

The K-th powers can be computed in \mathcal{O}(\log K) using binary exponentiation, and the binomial coefficients can be computed in \mathcal{O}(1) or \mathcal{O}(\log N) time by precomputing factorials and inverse factorials.

TIME COMPLEXITY:

\mathcal{O}(N \log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
N = 200005
mod = 998244353
fac = [1] + list(range(1, N))
for i in range(1, N): fac[i] = (fac[i-1] * i) % 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, k = map(int, input().split())
    ans = 0
    
    for m in range(1, n+1):
        ans += (pow(m, k, mod) - pow(m-1, k, mod)) * C(n-m, n-k) % mod
    print(ans % mod)
1 Like