MINMODSUB - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Stars and bars

PROBLEM:

For a parameter M and an array A, define:

  • S(i, j) = A_i + \ldots + A_j
  • T(i, j) = \min(S(i, j) \bmod M, (M - S(i, j)) \bmod M)
  • f(A) = \min_{1 \le i \le j \le N} T(i, j)

You’re given M.
For each N = 1, 2, \ldots, M, compute the sum of f(A, M) across all arrays A of length N containing integer elements in [1, M].

EXPLANATION:

It’s important to first understand exactly what f(A) is.
S(i, j) is of course just the subarray sum from index i to index j.
T(i, j) is then a measure of how “close” S(i, j) is to being a multiple of M.
So, f(A, M) represents the closest a subarray sum of A is to being a multiple of M.

Given that we’re dealing with subarray sums, it’s helpful to look at things in terms of prefix sums of A.
So, let P_i = (A_1 + A_2 + \ldots + A_i) \bmod M be the i-th prefix sum of A modulo M.
Note that we also have P_0 = 0.

f(A, M) is now the smallest difference between any two elements of P; where the difference is “circular”.
That is, imagine a circle with M equally spaced point on it (labeled 0, 1, \ldots, M-1).
On this circle, place each P_i at its corresponding label; and then f(A, M) simply represents the minimum distance along this circle of some P_i and P_j.

With the above characterization in hand, let’s try to compute the answer for a fixed N and M.

That is, we want to sum up f(A, M) across all M^N arrays.
To do this, we use the contribution technique: that is, we’ll fix the value of K = f(A, M), and count the number of arrays A that satisfy this; then multiply this count by K.
Summing this up across all K will give us the necessary sum.

So, on top of N and M, let’s also fix the value of K = f(A, M), and try to count the number of arrays with answer exactly K.

To have f(A, M) = K, in terms of what we saw with the circle earlier, K must be the minimum distance between a pair of prefix sums on the circle.
Note that if we know the prefix sums modulo M, we also uniquely know the array A (as A_i = (P_i - P_{i-1})\bmod M).
So, counting arrays A is equivalent to counting prefix sum arrays P; and we hence focus on counting prefix sum arrays.

Our goal is now to count the number of ways of placing N prefix sums along the M-circle such that the minimum difference between some pair of elements is exactly K.
The minimum difference will clearly come from some adjacent pair of elements along the circle.
Note that if K \gt 0, in particular this means no two prefix sums can be equal (since that would be a difference of 0 otherwise).
So, we’ll choose N distinct points along the circle to be the prefix sums - and once the points are chosen, any ordering of them will be valid.
Thus, to count the number of valid arrays, we can instead count the number of ways of choosing a valid subset, and multiply that by N!.

Note that we’re forbidden from picking 0 as one of the N points though, since P_0 = 0 always.

Our aim is now to count the number of choices of subsets of \{1, 2, \ldots, M-1\} such that the minimum difference between some pair of adjacent elements is K.
This is equivalent to counting subsets such that:

  1. Every adjacent difference is at least K.
  2. At least one adjacent difference is exactly K.

Let’s focus on the first one for now.
Suppose we choose the elements x_1, x_2, \ldots, x_N.
Then, we must have:

  • x_1 \ge K (since 0 is always picked, being P_0, we must be K away from it too).
  • x_2 - x_1 \ge K
  • x_3 - x_2 \ge K
    \vdots
  • x_N - x_{N-1} \ge K
  • M - x_N \ge K (because of circularity, the last element cannot be too close to 0 either).

Essentially, we have N+1 differences, and each of these differences must be at least K each.
Further, if we denote these differences as d_1, d_2, \ldots, d_{N+1}, then their overall sum d_1 + d_2 + \ldots + d_{N+1} must be exactly equal to M; since it represents us starting at 0 and ending up at M, and the segment [0, M] has length M.

Note that counting valid configurations of differences is equivalent to counting valid subsets, so we can just count the configurations of differences.
That is, we’re interested in counting the number of ways of assigning d_i such that

d_1 + d_2 + \ldots + d_{N+1} = M \hspace{20pt} \text{and} \hspace{20pt} \forall 1 \le i \le N+1, d_i \ge K

By subtracting K from each d_i, this is equivalent to computing the number of non-negative integer solutions to

d_1 + d_2 + \ldots + d_{N+1} = M - (N+1)\cdot K

which is a direct application of stars and bars, and is just \binom{M - (N+1)\cdot K + N}{N}.

Note that the above binomial coefficient simply gave us the number of configurations where each adjacent distance is at least K.
We want the number of configurations that satisfy this, but also have at least one adjacent difference being exactly K.
This is easy: simply subtract out the number of configurations whose adjacent differences are all \ge K+1, which can be computed similarly in \mathcal{O}(1).

We thus know how to solve for a fixed tuple (N, M, K).
To solve for just (N, M), we need to sum up the above quantity for all possible values of K.
This immediately gives us a quadratic solution, just running it for each value of N.

Now, observe that there’s one simple optimization that can be made: for (N, M, K), if we have M - (N+1)\cdot K \lt 0, then there are surely no solutions to the expression

d_1 + d_2 + \ldots + d_{N+1} = M - (N+1)\cdot K

So, rather than trying every K from 0 to M-1, we only need to try for “small” enough K, which means K \le \frac{M}{N+1}.

Thus, solving for N requires a runtime of only \mathcal{O}\left(\frac{M}{N+1}\right) rather than \mathcal{O}(M).
Summing this up across all 1 \le N \le M brings the complexity to \mathcal{O}(M \log M) due to it being the Harmonic summation multiplied by M, which is now fast enough!

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
N = 4 * 10**5
mod = 998244353
fac = [1]*N
for i in range(1, N): fac[i] = fac[i-1] * i % mod
inv = fac[:]
inv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N-1)): inv[i] = inv[i+1] * (i+1) % mod
def C(n, r):
    if n < r or r < 0: return 0
    return fac[n] * inv[r] * inv[n-r] % mod

for _ in range(int(input())):
    m = int(input())
    ans = []
    for n in range(1, m+1):
        cur = 0
        for k in range(1, m+1):
            if m - (n+1)*k < 0: break
            cur += C(m - (n+1)*k + n, n)
        ans.append(cur * fac[n] % mod)
    print(*ans)
5 Likes
2

Such a beautiful explanation!

3

The sample code does NOT subtract those with adjacent differences are at least K+1, but it also ignores multiplying K. The complete formula is:

int T;
cin >> T;
while (T--) {
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    Mint ans = 0;
    for (int k = 1; k <= ((m + i) / (i + 1)); k++) {
      // k * (count of differences with at least one k) * n!
      ans += k * (C(m - 1ll * (i + 1) * k + i, i) - C(m - 1ll * (i + 1) * (k + 1) + i, i)) * Fact(i);
    }
    cout << ans << " \n"[i == m];
  }
}