### PROBLEM LINK:

**Author:** Sergey Nagin

**Tester:** Jingbo Shang

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

EASY

### PREREQUISITES:

High school maths, Inclusion-exclusion principle, Modular exponentiation

### PROBLEM:

Given three integers N, M and Q, find the number of sequences of N elements, with each element in [1, M] such that the difference between the maximum and minimum element of the sequence is Q.

### QUICK EXPLANATION:

If we fix the minimum value of the sequence to an integer a, then the maximum value of the sequence is b = a + Q. Now consider the following four values:

A = number of sequences on N elements, with each element in [a, b],

B = number of sequences on N elements, with each element in [a, b - 1],

C = number of sequences on N elements, with each element in [a + 1, b], and

D = number of sequences on N elements, with each element in [a + 1, b - 1].

The number of N-element sequences with each element in [a, b] satisfying the constraint that

- at least one element of the sequence is equal to a, and,
- at least one element of the sequence is equal to b, is given by

(A - B - C + D).

The number of N-element sequences with element in the range [x, y] is given by N^{y - x + 1}, as each element of the sequence has (y - x + 1) choices. Hence, the number of sequences satisfying the above constraints will be:

(Q + 1)^{N} - 2 * Q^{N} + (Q - 1)^{N}.

Since the value of “a” can be anything in the range [1, M - Q], the number of sequences with the max-min difference constraint is (M - Q) times the above expression.

Special care has to be taken for the case when M <= Q, in which case there are no valid sequences.

### EXPLANATION:

Serja starts with a sequence of N elements, and applies a specific transformation

k times. After that he computes the difference between the maximum and minimum element of the resulting sequence. He wants to know how many starting sequences with each element in range [1, N] will produce the same max-min difference Q after k transformations.

### Invariance of max-min difference:

The first observation to make is that the transformation does not alter the difference between maximum and minimum element of the sequence.

Assume that we have a sequence a_{1}, a_{2}, …, a_{N}.

Let us define two new variables

m = min(a_{1}, a_{2}, …, a_{N}),

s = a_{1} + a_{2} + … + a_{N}

After the transformation the sequence becomes b_{1}, b_{2}, …, b_{N} given by

m + s - a_{1}, m + s - a_{2}, …, m + s - a_{N}

Note that,

(b_{i} - b_{j}) = (m + s - a_{i}) - (m + s - a_{j}) = -(a_{i} - a_{j}).

This means that after the transformation, the order of element is reversed, hence if a_{i} was the maximum (minimum) of the original sequence, then b_{i} will be the minimum (maximum) of the new sequence.

Let us say that a_{i1} was the smallest element of the original sequence, and a_{i2} was the largest element of the original sequence. After transformation b_{i2} will be the smallest element and b_{i1} will be the largest element.

The difference between the new maximum and new minimum element is

b_{i1} - b_{i2} = -(a_{i1} - a_{i2}) = (a_{i2} - a_{i1})

which is the same as the difference between the largest and smallest element of the original sequence.

This means, we can ignore the transformation completely, and now our problem has been reduced to find the number of N-element sequences with each element in [1, M] such that the difference between maximum and minimum element of the sequence is equal to a given value Q.

### Case when Q = 0:

The problem constraints specify that Q >= 1, hence this case will never occur. If the value of Q was allowed to be 0, then in that case the answer would be M, as all elements of the sequence should be the same and can take any of the values from 1 to M.

### Case when M is too small (M <= Q):

Since all elements of the sequence are chosen from the range [1, M], the maximum difference between two element can be (M - 1). If the desired max-min difference Q is larger than this value, then we certainly cannot construct any such sequence.

In other words, if (M <= Q), then the answer is 0.

### Case when M > Q > 0:

Since the difference between maximum and minimum element of the sequence is Q, the possible candidate for the minimum and maximum elements are

(1, 1 + Q)

(2, 2 + Q)

…

(M - Q, M)

Now, let us find out the number of N-element sequence with minimum value a and maximum value b.

First, let us find the number of sequences, where all elements are in the range [a, b]. Since any element of the sequence can take any value in the range [a, b], i.e., it has (b - a + 1) choices, the number of such sequences is given by

A = (b - a + 1)^{N} = (Q + 1)^{N}

Although all the elements are in the range [a, b], it is possible that none of the element of the sequence is equal to a, or b. Hence, we need to remove those sequences which do not contain either a or b.

Let

B = number of sequences with elements in [a, b], but none equal to b

C = number of sequences with elements in [a, b], but none equal to a

D = number of sequences with elements in [a, b], but none equal to a, b. These are the sequences which have been counted in both B and C

Hence, the number of sequences with elements in [a, b] which do not contain either a or b, will be given by (B + C - D).

Further, we can see the following definitions of B, C and D are equivalent:

B = number of sequences with elements in [a, b - 1]

C = number of sequences with elements in [a + 1, b]

D = number of sequences with elements in [a + 1, b - 1]

Equivalently,

B = (b - a)^{N} = Q^{N}

C = (b - a)^{N} = Q^{N}

D = (b - a - 1)^{N} = (Q - 1)^{N}

Therefore, the number of subsequences with elements in [a, b] and having at least one element equal to a, and at least one element equal to b, is given by

A - (B + C - D) = (Q + 1)^{N} - 2Q^{N} + (Q - 1)^{N}.

Note that the number of sequences is independent of a and b, and only depends on Q. We have (M - Q) candidate pairs for (a, b) as shown above. Hence, the answer will be

(M - Q) * ((Q + 1)^{N} - 2Q^{N} + (Q - 1)^{N})

### Modular exponentiation

Finally, in order to compute the value of (Q + 1)^{N}, Q^{N}, (Q - 1)^{N} we need to use the modular exponentiation, which have been the part of many problems of previous contests. Here is the snippet that does the same.

// Calculates x^y mod P power(x, y, P uint64_t) uint64_t { if (y == 0) return (1 % P); t := power(x, y/2, P); t = (t * t) % P; if (y & 1) t = (t * x) % P; return t; }

### Time Complexity:

O (lg N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution can be found here.