PROBLEM LINK:
[Contest(Mirror)][1]
[Practice][2]
Setter-[Akashdeep Nain][3]
Tester-
Editorialist- [Abhishek Pandey][4]
DIFFICULTY:
HARD
PRE-REQUISITES:
Math, Math AND MORE MATH. Namely- [Generating Functions][5] ,[Using Binomial Coefficients in Combinatorics][6], [Luca’s Theorem][7], [Fast Exponentiation][8] .
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