PROBLEM LINKS
DIFFICULTY
HARD
PREREQUISITES
Generating Functions, Partial Function Decomposition, Complex Numbers
PROBLEM
In a currency there are N denominations of coins, given as an array D. All elements in D are pairwise distinct and pairwise relatively prime.
Can you use this property of the coinage to design a fast algorithm to answer queries of the type
 How many ways exist of making change for target S? Of course, the answer should be found modulo MOD.
EXPLANATION
There is a popular technique for creating a generating function for this the number of ways of making change. Let us quickly look at the appropriate generating function that gives us the answer.
G(x) = PROD ( SUMMA ( x^{u * d}, 0 ≤ u < ∞ ), d ∈ D )
The coefficient of x^{S} in G(x) (modulo MOD), will be the answer.
We can multiply and divide each term inside the product in G(x) with (1x^{d}). This gives us the following simplified expression for G(x)
1 PROD (  , d ∈ D ) ... (i) 1  x^{d}
We can rewrite (i) as
1 1  * PROD (  , d ∈ D ) ... (ii) (1  x)^{n} 1 + x + x^{2} + ... x^{d1}
For some polynomial,
f(x) = 1 + x + x^{2} + ... x^{n1}
And an complex n^{th} root of unity w_{n},
w_{n} = e^{ι 2π/n}
We can easily prove that
f(w_{n}^{i}) = 0, 1 ≤ i < n
Thus, we can factorize f(x) as
(x  w_{n}) (x  w_{n}^{2}) ... (x  w_{n}^{n1})
Now, we can transform (ii) into
1 1  * PROD ( PROD (  , 1 ≤ i < d ) , d ∈ D ) ... (iii) (1  x)^{n} x  w_{d}^{i}
From the problem description, we are assured that all d are pairwise prime. This is a very important because this means that all w_{d}^{i} are also pairwise distinct! This means that each w_{d}^{i} is a simple root of the denominator. Hence, the Partial Fraction Expansion of
1 PROD ( PROD (  , 1 ≤ i < d ) , d ∈ D ) ... (iv) x  w_{d}^{i}
Can eventually be written as
P(w_{d}^{i}) SUM ( SUM (  , 1 ≤ i < d ) , d ∈ D ) ... (v) x  w_{d}^{i}
Let us find P(x). Note that P(x) will depend on d. Hence all the calculations below should be assumed to already be within the closure with i and d available from (v).
We know that
1
1
PROD ( 1 + x + x^{2} + … x^{d’1} , d’ ∈ D )
P(w<sub>d'</sub><sup>j</sup>)
= SUM ( SUM (  , 1 ≤ j < d ) , d' ∈ D ) ... (vi)
x  w<sub>d'</sub><sup>j</sup>
Let us multiply the LHS and RHS with (x  w_{d}^{i}).
x  w_{d}^{i}
x  w_{d}^{i}
PROD ( 1 + x + x^{2} + … x^{d’1} , d’ ∈ D )
P(w<sub>d'</sub><sup>j</sup>)
= (x  w<sub>d</sub><sup>i</sup>) * SUM ( SUM (  , 1 ≤ j < d' ) , d' ∈ D ) ... (vii)
x  w<sub>d</sub><sup>i</sup>
Now, let us keep x = w_{d}^{i} in (vii).
 The RHS reduces to P(w_{d}^{i}), since all other terms become 0.
 The LHS becomes of the form 0 / 0
 But we know that this function is well defined for all real x
Thus, we use the L’Hopital’s rule for the LHS and take the derivatives of the numerator and the denominator. Out of the N terms in the first derivative of the denominator of the LHS we note that only one of them is non zero. Hence, we get
1 P(w_{d}^{i}) =  (1 + 2w_{d}^{i} + 3w_{d}^{2i} + ... (d1)w_{d}^{(d2)i}) * PROD ( 1 + w_{d}^{i} + w_{d}^{2i} + ... w_{d}^{(d'1)i} , d' ∈ D AND d' ≠ d )
Now let us simplify the above a bit. We use the Sum of AGP to simplify the first term. We also use
 w_{d}^{d} = 1

SUM ( w_{d}^{i} , 0 ≤ i < d ) = 0
 we used this above already when we said that all except one term in the first derivative of the denominator of the LHS will be 0
to further simplify things above.
For simplicity, let us define P(d,y). y will always be a complex d^{th} root of unity.
y * (y  1) P(d,y) =  d * PROD ( SUM ( y^{i}, 0 ≤ i ≤ (d' modulo d) ), d' ∈ D )
Now, expression for G(x) looks like
1 P(w_{d}^{i})  * SUM ( SUM (  , 1 ≤ i < d ) , d ∈ D ) ... (viii) (1  x)^{n} x  w_{d}^{i}
We use the following Partial Fraction Decomposition to furthur break down the above
1 1  *  (1  x)^{n} (x  y) 1 1 =  + SUM (  , 1 ≤ i ≤ N) (1  y)^{N} * (x  y) (1  y)^{Ni+1} * (x  1)^{i}
(This too can be proven easily by repeatedly using the L’Hopital’s Rule!)
Now, we have G(x) broken into non reducible fractions.
P(d,w_{d}^{i}) P(d,w_{d}^{i}) G(x) = S_{D}( S_{i} (  + S_{j} (  ) ) ) (1  w_{d}^{i})^{N} * (x  w_{d}^{i}) (1  w_{d}^{i})^{Nj} * (x  1)^{j} Where, 0 ≤ j < N 1 ≤ i < d d ∈ D
Now, we can use the Generalized Binomial Theorem to find the coefficient of x^{S} in G(x). The expression for the coefficient will look like
U_{d}(w_{d}^{i}) SUM ( SUM (  , 1 ≤ i < d ) , d ∈ D ) V_{d}(w_{d}^{i})
Let, Q_{d}(x) = 1 + x + x^{2} + … x^{d1}
As we can see above, we want to calculate
 U_{d}(y) / V_{d}(y) for some y, such that Q_{d}(y) = 0
Let Z_{d}(y) be a polynomial of degree strictly less than d1 such that
 V_{d}(y) * Z_{d}(y) = 1 modulo Q_{d}(y) = 0
This means that
 V_{d}(y) * Z_{d}(y) = 1 + R_{d}(y) * Q_{d}(y)
Now,

1 / V_{d}(y) = Z_{d}(y) / (V_{d}(y) * Z_{d}(y))
 = Z_{d}(y) / (1 + R_{d}(y) * Q_{d}(y))
But, Q_{d}(y) = 0 for all y that we want to evaluate V_{d}(y) for.
Thus, we can run the Extended Euclid’s Algorithm for univariate polynomials with coefficients in a field to find the inverse of V_{d}(y) modulo Q_{d}(y).
This gives us a polynomial T_{d}(y) to play with!
The answer will be
SUM ( SUM ( T_{d}(w_{d}^{i}) , 1 ≤ i < d ) , d ∈ D )
But, calculating T_{d}(y) requires a lot of calculations in complex numbers whose coefficients are irrational. We cannot find the result modulo MOD just with this knowledge yet.
Now comes another proof that simply eliminates all the complex numbers from all the calculations!
Let
T_{d}(y) = t_{0} + t_{1}y + t_{2}y^{2} + ... t_{d1}y^{d1}
We can infer from all the above discussions that
 U_{d}(y) has degree 1
 Z_{d}(y) has degree d2
 Thus, T_{d}(y) has degree d1
SUM ( T_{d}(w_{d}^{i}) , 1 ≤ i < d ) = SUM ( t_{p} * SUM ( w_{d}^{i * p} , 1 ≤ i < d ) , 0 ≤ p < d ) = SUM ( t_{p} * SUM ( w_{d}^{i * p} , 1 ≤ i < d ) , 1 ≤ p < d ) + t_{0} * (d  1) We know that Q_{d}(w_{d}^{p}) = 0 for any nonzero t. Thus, SUM ( w_{d}^{i * p} , 1 ≤ i < d ) = 1 We can simplify the above as = SUM ( t_{p}, 1 ≤ p < d ) + t_{0} * (d  1) = d * t_{0}  SUM ( t_{p} , 0 ≤ p < d ) = d * T_{d}(0)  T_{d}(1)
This allows us to use the polynomial Z_{d}(y) that we generated for evaluation only for 0 and 1.
It is worth noting that the large S is not a problem at all while solving the problem. It appears only in the exponent of w_{d}. This lets us consider S modulo d conveniently.
Doing this for each d, solves the problem.
There lie several simplifications to the polynomials along the way that can be exploited to make the code neater.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.