PROBLEM LINK:
Setter-Akashdeep Nain
Tester-
Editorialist- Abhishek Pandey
DIFFICULTY:
HARD
PRE-REQUISITES:
Math, Math AND MORE MATH. Namely- Generating Functions ,Using Binomial Coefficients in Combinatorics, Luca’s Theorem, Fast Exponentiation .
Please read about Generating Functions before reading the editorial if its a new concept to you. That is because, its not possible for me to derive every possible result and reason how and where its used (The editorial will be extremely long and boring then). Hence, please google out things and read about Generating Functions and grasp the concept.
Word from Editorialist- This editorial will also have some hand exercises for the interested ones. They will be there to make yourself work up and hence aid your intuition in deducing things so that you can develop that sixth sense when you encounter such a problem, and so that you can understand the editorial better. I will try my best to explain the concepts as easily as possible 
PROBLEM:
Given 2 type of chips, square and hexagonal, you have to spend exactly N bitcoins to buy exactly A square and B hexagonal chips. With this, you are expected to give \sum\limits_{i=1}^n Signal Strength where SignalStrength=\prod\limits_{i=1}^n p_i
QUICK EXPLANATION:
Using the concepts of generating functions, we get to know that the answer is {x}^{n} in the series {6}^{B}* {x}^{A+B}* {(1 + x)}^{A}* {(1 - x)}^{-3A - 3B}. Once this is deduced, we can easily calculate the required answer using Luca's Theorem for values of n\choose r and Fast Exponentiation to avoid TLE in the process.
EXPLANATION:
The explanation will be divided into 3 parts-
- Telling about Generating function of Square and Hexagonal chips and significance of coefficients.
- How to deal with constraint of exact A square and exact B Hexagonal chips.
- Final calculations.
1.Generating functions and significance of the coefficients-
To anyone having a basic idea about generating functions, the intuition must had been to attempt to write the generating functions for Square and for Hexagonal chips. Its not hard at all to deduce that the generation function for square chips , say F(x) is-
F(x)=x+4{x}^{2}+9{x}^{3}+16{x}^{4}.....
To those who are having trouble interpreting generating function concept, look at the coefficient of {x}^{n} in above. Lets consider 4{x}^{2}. What is the significance of it? It is, that, 4 is the number of nano-particles you get if you spend all of N money in buying a square chip of that size. You can compare all terms similarly.
Q1- Can you attempt to deduce what can be the function for Hexagonal chips? (Hint: Follow the analogy above)
.
.
.
.
As intuition goes, the function for Hexagonal chips, say G(x), is-
G(x)= 6x + 18{x}^{2} + 36{x}^{3} +.....
You can see that similar analogy holds here as well.
Now, this analogy assumes that we are spending all N bitcoins in buying a single chip and gives the required nano-particles as the coefficient. But how will we use and expand this to follow the constraint in question on exactly A square and exactly B hexagonal chips?
2.Fulfilling the constraint of exactly A and B chips respective shapes-
This is achieved by raising the respective generating functions to power A and B. Meaning-
F(x)={F(x)}^{A}={(x+4{x}^{2}+9{x}^{3}+16{x}^{4}........)}^{A}
G(x)={G(x)}^{B}={(6x + 18{x}^{2} + 36{x}^{3} +.....)}^{B}
Ca you see any intuitive reason why this is helping? For one, raising the function F(x) to power A means that the least term we encounter is 1{x}^{A}. It is the case when all A coins are spent on buying square chips of size 1. Can we expand this reasoning?
Lets take a simple example. Take N=3 and A=2. Lets ignore B and hexagonal chips for the moment.
{F(x)}^{2}={(x+4{x}^{2}+9{x}^{3}+16{x}^{4}........)}^{2}={x}^{2}+8{x}^{3}+34{x}^{4}....
Lets consider the term,{x}^{n}={x}^{3}, i.e. 8{x}^{3}. What does it represent? It is the number of nano-particles spent when we have to buy exactly 2 square chips and spend a total of 3 bitcoins. It considers both cases, of (1,2),(2,1). This is exactly what we need to know!
Question 2- Consider the case of N=3, B=2 , A=0. What is the generating function of hexagonal chips then? What is the coefficient of x^3 in it? Can the above reasoning hold here as well?
Till now we had considered only square chips. How to go about when hexagonal chips kick in as well? Also, finding the power of generating function is not at all an easy job. How to get over it?
3.Calculating the final answer-
Now, we know that {F(x)}^{A} and {G(x)}^{B} are the generating functions when we have to buy exactly A and B chips respectively. Further, we know that if we have to spend exactly N bit coins, then we need to look up the coefficient of {x}^{n} in the expansion.
Now, since SignalStrength=\prod\limits_{i=1}^n p_i , where p_i is the number of nano-particles in square or hexagonal chips, its natural to see that our answer is coefficient of {x}^{n} in {(F(x))}^{A}*{(G(x))}^{B}. Meaning-
Answer= Coefficient of {x}^{n} in {(x+4{x}^{2}+9{x}^{3}+16{x}^{4}........)}^{A} * {(6x + 18{x}^{2} + 36{x}^{3} +.....)}^{B}
Now, how to proceed next? After some paperwork, you will find that the final expression is-
{(x+4{x}^{2}+9{x}^{3}+16{x}^{4}........)}^{A} * {(6x + 18{x}^{2} + 36{x}^{3} +.....)}^{B}={6}^{B}* {x}^{A+B}* {(1 + x)}^{A}* {(1 - x)}^{-3A - 3B}
(The derivation has been given in Chef Vijju’s corner for the interested ones)
Now we have to find coefficient of {x}^{n} in this. For {(1+x)}^{A} we can easily find coefficient of {x}^{r} as n\choose r {1}^{n-r} {x}^{r}. For coefficient of {x}^{k} in {(1 - x)}^{-3A - 3B} the formula is (n+k-1)\choose k {x}^{k}.
Now, look at the final expression. We have already taken out {x}^{A+B}, so we need to find coefficients such that r+k=N-A-B. We see that the number of terms in {(1+x)}^{A} is A+1. We can loop through all the coefficients in this and multiply with the corresponding coefficients in the second series of {(1 - x)}^{-3A - 3B} (since this has infinite terms).
For calculating, we need the values of n\choose r and corresponding (n+k-1)\choose k . To calculate this, we can easily use Luca’s Theorem and fast exponentiation. You can refer to Editorialist’s solution for details.
EDITORIALIST’S SOLUTION:
TimeComplexity=O(ALogN)
CHEF VIJJU’S CORNER:
- The derivation of the expression deserves to be given first.
2.If you have got the concept correctly, can you at least tell what would be the answer, can you tell what the answer would be if I ask for you need to buy **AT LEAST** A square and **AT LEAST** B Hexagonal chips ?
3.Consider this implementation of fast exponentiation for this question-
long long Fast_Exponentiation(long long num, long long power)
{
if(power==1)return num;
else if(power==2)return (num*num)%mod;
else
{
return Fast_Exponentiation(num,power/2) * Fast_Exponentiation(num,(power+1)/2);
}
}
With reference to above code, answer the following-
i)Compare its run-time to normal looping method - for(i=1;i<=n;i++)ans=(ans*num)%mod;. Is the performance better than this, equal to this, or worse than this?
ii) Would you recommend using this implementation of fast exponentiation? Why/Why not?
4.The setter had an unfulfilled wish of giving this problem to you guys as a bonus-
Challenge problem: Solve for the case when hexagonal chips don’t have a hole in center. Can you solve it?