PROBLEM LINK:
Author: Bruno Oliveira
Tester: Hiroto Sekido
Editorialist: Anton Lunyov
DIFFICULTY:
SIMPLE
PREREQUISITES:
Simple Math
PROBLEM:
Let Messi have index 0, while all other players have indexes from 1 to K.
Denote as f[n][x] the number of sequences {a[0], a[1], …, a[n]} of integers such that:
- 0 ≤ a[j] ≤ K for j = 0, 1, 2, …, n;
- a[0] = 0, a[n] = x;
- a[j−1] ≠ a[j] for j = 1, 2, …, n.
We need to find f[N][0] mod P, where P = 1000000007.
QUICK EXPLANATION:
Let K be fixed and g[n] denotes f[n][0] mod P. Then g[0] = 1, g[1] = 0 and
g[n] = ((K − 1) * g[n−1] + K * g[n−2]) mod P for n ≥ 2.
See EXPLANATION for proof.
So the problem can be solved using simple loop. But be careful with modular arithmetic. The following code:
g[n] = ((long long) (K-1) * g[n-1] + (long long) K * g[n-2]) % 1000000007;
is safe at C++ for calculating g[n] for the above recurrence. Not writing long long
will cause int
overflow.
Alternatively the problem can be solved using formula (K^{N} + K * (−1)^{N}) / (K + 1). But using this formula requires either inverse residue modulo P or arbitrary precision arithmetic. So use it on your own risk
See ALTERNATIVE SOLUTION for details.
EXPLANATION:
At this section we justify recurrence for g[n].
It is clear that f[0][0] = 1 and f[0][x] = 0 for x = 1, …, K.
Basic combinatorial reasoning yields that f[n][x] for n > 0 is the sum of f[n−1][y] for all y from 0 to K, inclusive, such that y ≠ x. Indeed, term a[n−1] can be any number from 0 to K, inclusive, except x. So after fixing y = a[n−1] and deleting a[n] we get the arbitrary sequence that is counted by f[n−1][y].
The constraints are very soft. So even such quadratic DP will pass the TL, but we continue further.
It is clear that f[n][1] = f[n][2] = … = f[n][K] since all players except Messy are non-distinguishable by the above definition. Hence denoting g[n] = f[n][0] and h[n] = f[n][1] we can get the following formulas for g[n] and h[n]:
g[n] = f[n][0] = f[n−1][1] + … + f[n−1][K] = K * h[n−1];
h[n] = f[n][1] = f[n−1][0] + f[n−1][2] + … + f[n−1][K] = g[n−1] + (K−1) * h[n−1].
Summarizing we get:
g[0] = 1, h[0] = 0,
g[n] = K * h[n−1],
h[n] = g[n−1] + (K−1) * h[n−1].
By theses formulas we already get simple O(N) solution (refer to the tester’s solution).
But we can get another simplification.
Multiplying formula for h[n] by K we get:
K * h[n] = K * g[n−1] + (K−1) * (K * h[n−1]).
Note that K * h[n] = g[n+1] and K * h[n−1] = g[n].
Hence we get
g[n+1] = K * g[n−1] + (K−1) * g[n] for n > 1.
Together with g[1] = K * h[0] = 0 we get the solution described in the QUICK EXPLANATION section.
Note also that using exponentiation by squaring for 2 × 2 matrices we can solve the problem in O(log N) time using recurrent formulas for g[n] and h[n]. Most of the related problems listed below require similar considerations but also require some advanced technique like exponentiation by squaring in the end.
ALTERNATIVE SOLUTION:
Here we prove the explicit formula mentioned in the QUICK EXPLANATION section.
We apply the basic theory of linear homogeneous recurrence relations with constant coefficients to the recurrent sequence g[n]. For this we write down the characteristic polynomial:
Its roots are r_{1} = −1 and r_{2} = K. Hence the general solution for this recurrence is
**g[n] = C_{1} * r_{1}^{N} + C_{2} * r_{2}^{N} = C_{1} * (−1)^{N} + C_{2} * K^{N}**.Constants C_{1} and C_{2} can be found from relations g[0] = 1, g[1] = 0.
Namely, substituting n = 0 and n = 1 to the general form of g[n] we get
Solving this 2 × 2 system we get C_{1} = K / (K + 1) and C_{2} = 1 / (K + 1).
Hence g[n] = (K^{n} + K * (−1)^{n}) / (K + 1) and we are done.
The simplest way to use this formula is to use language with built-in arbitrary precision arithmetic like Java or Python and calculate the above expression directly and then take it modulo P in the end.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
RELATED PROBLEMS:
Codeforces Round #113 (Div. 2) - Problem E - Tetrahedron
NEWSCH
CKISSHUG
CROWD
CSUMD
CHESSGM
HAREJUMP
CAKEDOOM