Questions Tagged With matrix-expohttps://discuss.codechef.com/tags/matrix-expo/?type=rssquestions tagged <span class="tag">matrix-expo</span>enThu, 04 Jan 2018 22:42:45 +0530Help please for matrix exponentiation based GROWGOLDhttps://discuss.codechef.com/questions/7669/help-please-for-matrix-exponentiation-based-growgold<p>My <a href="http://www.codechef.com/viewsolution/1959063">code</a> gives correct answers:</p>
<p>tax[7] = tax[3] * tax[4] * tax[5] * tax[6] = 3 * 4 * 8 * 16 = 1536</p>
<p>tax[8] = 4<em>8</em>16*1536 = 786,432</p>
<p>tax[9] = 8 * 16 * 1536 * 786,432 = 18811834</p>
<p>tax[10] = 16 * 1536 * 786,432 * 18,811,834 = 84,208,956</p>
<p>tax[11] = 1536 * 786432 * 18811834 * 84208956 = 35889352</p>
<p>tax[12] = 786432 * 18811834 * 84208956 * 35889352 = 75453662</p>
<p>tax[13] = 18811834 * 84208956 * 35889352 * 75453662 = 44609468</p>
<p>But still I am getting Wrong Answer :(</p>
<p>(<a href="http://ideone.com/scwT0S">ideone link</a>.)</p>monish001Sun, 24 Mar 2013 12:54:41 +0530https://discuss.codechef.com/questions/7669/help-please-for-matrix-exponentiation-based-growgoldgrowgoldmatrix-expoJacobsthal numbershttps://discuss.codechef.com/questions/12408/jacobsthal-numbers<p><strong>Jacobsthal numbers</strong> are analogous to fibonacci numbers </p>
<p>their series is <strong>0 1 1 3 5 11 21 43 85.....</strong>
Now I came across an interesting problem where i found use of this not so well-known series </p>
<p>if u want to know more abt this series <a href="http://en.wikipedia.org/wiki/Jacobsthal_number">LINK</a></p>
<p>The problem is : </p>
<p><strong>PROBLEM STARTS HERE</strong></p>
<p>The problem setter for this contest is also setting up problems for IHPC (in Techkriti).
There, he encountered a new field of writing parallel code and a totally new thinking style to go about solving algorithmic problems by doing computations in parallel.
He created the following problem:
He takes N processors numbered 1, 2, ..., N. Each processors is initially given a number Ci and then all of them perform the following process in parallel:
First, each processor finds the sum of the numbers of the other N-1 processors.
After all processors are finished, each processor replaces its number with the sum it computed. To avoid very large numbers, the processors will keep track of their numbers modulo 98,765,431.
To make it more tough, he sets the processors to repeat this algorithm T times.
After thinking a bit more on the problem, he realised that this can also be solved very efficiently using sequential code instead. So, he decided to check if the Algorithmic community of IITK, the teams practicing for IOPC can solve it or not? </p>
<p>Constraints</p>
<p>1 ≤ N ≤ 50,000 </p>
<p>0 ≤ Ci < 90,000,000 </p>
<p>1 ≤ T ≤ 109 </p>
<p>Input</p>
<p>Each input file consists of a single test case. Line 1 contains two space-separated integers, N and T.</p>
<p>From Lines 2 .... N+1, line i+1 contains a single integer Ci. </p>
<p>Output
N lines, where line i contains a single integer representing the number computed by processor i
(modulo 98,765,431) at the end of the T iterations of the algorithm. </p>
<p>Sample Input </p>
<p>3 4</p>
<p>1</p>
<p>0</p>
<p>4</p>
<p>Sample Output</p>
<p>26</p>
<p>25</p>
<p>29</p>
<p><strong>PROBLEM ENDS</strong></p>
<p>Now i tried it solving using an example and derived a formula (I'm sure it's correct)</p>
<p>after <strong>t</strong> iterations the elements of the array will be : <strong>jt*(S) + (-1)^t(a)</strong></p>
<p>here jt -> 't'th jacobsthal number</p>
<p>a -> that particular element of array</p>
<p>S -> sum of all elements of array</p>
<p>Now that everything is set and i wrote code which produces jacobsthal numbers in linear time
that's giving me TLE :(
so please help me to find jacobsthal numbers in O(logn) time ( just like fibonacci numbers )</p>
<p>Thank You</p>rakeshbubli143Mon, 03 Jun 2013 14:27:20 +0530https://discuss.codechef.com/questions/12408/jacobsthal-numbersjacobsthalc++matrix-expocalculate f(n) = a*f(n-1) + b*f(n-2) matrix exponentiationhttps://discuss.codechef.com/questions/40666/calculate-fn-afn-1-bfn-2-matrix-exponentiation<p>Given f(1)=1 , f(2)=1 , and f(n) = 100*f(n-1)+200f(n-2) .<br>
Now , i have to calculate f(n) rof n upto 10^9 , so obvious approach id to use matrix exponentiation ..<br>
I came up with this logic , but it gives wrong output . Can you please explain the reason ?
It fails with n=3 , but i am not able to come up with how to resolve it .</p>
<pre><code>#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll m=1000000007;
ll x,y,z,w;
void ml(ll F[2][2],ll M[2][2])
{
x = ((F[0][0]%m)*(M[0][0]%m))%m + ((F[0][1]%m)*(M[1][0]%m))%m;
y = ((F[0][0]%m)*(M[0][1]%m))%m + ((F[0][1]%m)*(M[1][1]%m))%m;
z = ((F[1][0]%m)*(M[0][0]%m))%m + ((F[1][1]%m)*(M[1][0]%m))%m;
w = ((F[1][0]%m)*(M[0][1]%m))%m + ((F[1][1]%m)*(M[1][1]%m))%m;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
//cout<<F[0][0]<<" " <<F[0][1]<<" "<< F[1][0]<<" " <<F[1][1]<<endl;
}
void po(ll F[2][2],ll n)
{
if( n<=1)
return;
ll M[2][2] = {{100,200},{1,0}};
po(F,n/2);
ml(F,F);
if( n%2 != 0 )
ml(F,M);
}
ll f(ll n)
{
ll F[2][2] = {{100,200},{1,0}};
if(n<=2)
return 1;
po(F,n-1);
return F[0][0];
}
int main(){
freopen("input.txt", "rt", stdin);
ll ans,n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%llu",&n);
ans=f(n);
printf("%llu\n",ans);
}
return 0;
}
</code></pre>ac_c0derSun, 30 Mar 2014 14:29:10 +0530https://discuss.codechef.com/questions/40666/calculate-fn-afn-1-bfn-2-matrix-exponentiationfibonaccialgorithmmatrix-expoLinear Reccurrence - Harejumphttps://discuss.codechef.com/questions/5086/linear-reccurrence-harejump<p>I was solving harejump using matrix exponentiation. To do so we need the base matrix F1 containing the solutions for the first 15 nos. So i used standard dp to solve for the first 15 nos. and then used matrix exponentiation. Here's my AC <a href="http://www.codechef.com/viewsolution/1714517">solution</a>. However seeing other solutions, i noticed that they have not created the base matrix. <a href="http://www.codechef.com/viewsolution/731949">eg</a> but their solutions still work. So I wanted to know why isnt it necessary to precompute the answers for the first 15 nos.?</p>karan173Sun, 13 Jan 2013 18:55:32 +0530https://discuss.codechef.com/questions/5086/linear-reccurrence-harejumprecurrencematrix-exporuntime error in chttps://discuss.codechef.com/questions/7524/runtime-error-in-c<p>SIGSEGV(signal 11) - most common, 'segmentation fault';
how to remove this error</p>
<blockquote>
<blockquote>
<p>should not be marked as <em>community wiki</em></p>
</blockquote>
</blockquote>shahnawazahmadSun, 17 Mar 2013 15:21:52 +0530https://discuss.codechef.com/questions/7524/runtime-error-in-cmatrix-expoHow to construct the Base matrix in recursive relations ?https://discuss.codechef.com/questions/2330/how-to-construct-the-base-matrix-in-recursive-relations<p>In solving many recursive problems , like Flibonakkii ,sum of fib products , Tribonacci we can make use of matrix exponentiation . This can be done only after constructing the base matrices .</p>
<p>Please help me finding how to construct the base matrix for any recursive relation . ?</p>phanindharWed, 12 Sep 2012 01:12:59 +0530https://discuss.codechef.com/questions/2330/how-to-construct-the-base-matrix-in-recursive-relationsrecursionfibonaccimatrix-expoCBARS - Editorialhttps://discuss.codechef.com/questions/3706/cbars-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/CBARS">Practice</a><br>
<a href="http://www.codechef.com/NOV12/problems/CBARS">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p>Matrix Exponentiation</p>
<h1>PROBLEM</h1>
<p>In how many ways can a fill a matrix of size <b>a</b> by <b>b</b>, such that, there are no rectanlges of height and width more than 1, that contain only 0s or only 1s. </p>
<h1>QUICK EXPLANATION</h1>
<p>Since <b>a</b> can only be at most 6, you can consider filling the matrix one column at a time.</p>
<p>A column can be filled in at most <b>2<sup>a</sup></b> ways. You can build an matrix that represents whether a column of type <b>A</b> can be followed by a column of type <b>B</b>. This matrix must be exponentiated <b>n</b> times to get the final answer.</p>
<h1>EXPLANATION</h1>
<p>Let us call a rectagle that violates the constraint - that is, it is made up entirely of 0s (or entirely of 1s) and has a width and height, both more than 1 - an invalid rectangle.</p>
<p>It is easy to see that if an invalid rectangle must exist, then there also exists an invalid rectangle of dimensions <b>2x2</b>.</p>
<p>Corollarly: if we ensure while filling a column that we are not building an invalid rectangle of dimension <b>2x2</b>, then there can never exist an invalid rectangle in the finished matrix.</p>
<p>We are going to fill the matrix column by column.</p>
<p>Consider the following situation.
</p><pre>....................(x0)(y0)
....................(x1)(y1)
....................(x2)(y2)
....................(x3)(y3)
....................(x4)(y4)
....................(x5)(y5)
</pre><p></p>
<p>Let us assume that the matrix has been filled up to column <b>X</b> such that it contains no invalid rectangles. We add another column, call it column <b>Y.</b> We know that the matrix contains no invalid rectangles of size <b>2x2</b> until column <b>X.</b> We must ensure that addition of column <b>Y</b> does not add an invalid rectangle of dimension <b>2x2.</b></p>
<p>But since any <b>2x2</b> rectangles that addition of column <b>Y</b> can introduce can only at most overlap column <b>X,</b> we can ignore the state of the rest of the matrix!</p>
<p>Now, let <b>Bx = (x5, x4, x3, x2, x1, x0)</b> be the bitset that represents the values in column X. Similarly, let <b>By = (y5, y4, y3 y2, y1, y0)</b> represents the values that we intend to fill in column Y.</p>
<p><b>Y can follow X if and only if (Bx bitwise-and By) does not contain any consecutive 1s AND (Bx bitwise-or By) does not contain any consecutive 0s</b>.</p>
<p>We can no build a matrix <b>canFollow</b> of dimension <b>2<sup>a</sup></b> by <b>2<sup>a</sup></b> which represents whether some configuration of a column can be followed by another configuration in the next column.</p>
<p>Exponentiation of <b>canFollow</b> leads us to enumerating the number of ways of filling the columns such that the matrix does not contain any invalid rectangles. As an example, the <b>4x4</b> matrix for a = 2 is
</p><pre> 00 01 10 11
00 | 0 1 1 1 |
01 | 1 1 1 1 |
10 | 1 1 1 1 |
11 | 1 1 1 0 |
</pre><p></p>
<p>Adding all the values in the above matrix gives us the answer for <b>a = 2, b = 2</b>.</p>
<p>To get the answer for <b>a = 2, b = 3</b> - we multiply it with itself once.
</p><pre>| 3 3 3 2 |
| 3 4 4 3 |
| 3 4 4 3 |
| 2 3 3 3 |
</pre><p></p>
<p>The answer would thus be 50.</p>
<p>The answer for and <b>a</b> and <b>n</b> can similarly be found by raising the matrix of dimension <b>2<sup>a</sup></b> by <b>2<sup>a</sup></b> to the power <b>(n-1).</b></p>
<h1>SETTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/November/Setter/CBARS.c">here</a>.</p>
<h1>TESTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/November/Tester/CBARS.c">here</a>.</p>gamabuntaMon, 12 Nov 2012 18:30:40 +0530https://discuss.codechef.com/questions/3706/cbars-editorialsimplenov12editorialmatrix-expoCHEFWD - Editorialhttps://discuss.codechef.com/questions/2265/chefwd-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFWD">Practice</a><br>
<a href="http://www.codechef.com/SEP12/problems/CHEFWD">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p>Math, Repeated Squaring, Fibonacci Numbers</p>
<h1>PROBLEM</h1>
<p>Find the number of ways to go from 0 to N, taking steps of 1 or 2, and taking exactly 1 back-step on the way of -1 or -2.</p>
<h1>QUICK EXPLANATION</h1>
<p>Let us assume that Ciel takes <code>k</code> steps forward, then one back, and the rest forward.</p>
<p>The number of ways she can accomplish this is <code>fib(k) * [ fib(N-k + 1) + fib(N-k + 2) ]</code>; since she can take only 1 or 2 steps back.</p>
<p>We have to find a summation of the above sequence for all k between 1 and N-1 inclusive. We can see that this needs to us to find summation of the form<br>
∑<sub>k = 0 to N</sub><code>fib(k)*fib(N-k)</code></p>
<p>This is also known as the convolution of the fibonacci series onto itself. Once we know how to solve this convolution efficiently, we can solve the problem.</p>
<h1>EXPLANATION</h1>
<p>There are several ways <code>F(N) =</code> ∑<sub><code>k = 0 to N</code></sub><code>fib(k)*fib(N-k)</code> can be found.</p>
<p>Formulas regarding the same have been listed on <a href="http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Convolved_Fibonacci_sequences">Wikipedia</a> as well as <a href="http://oeis.org/A001629">OEIS</a>. Finding a couple of smaller values and searching on OEIS is a solution to many a problem that asks you to find the result for a sequence of numbers.</p>
<p>If you're into math, then using the concept of fibonacci polynomials, one can derive several relations as outlined in this wonderful <a href="http://www.fq.math.ca/Scanned/15-2/hoggatt1.pdf">paper</a>.</p>
<h3>I. F(N) = F(N-1) + F(N-2) + fib(N)</h3>
<p>You can use the above identity and build a <code>4x4</code> matrix as follows
</p><pre> |1 1 0 0|
[F(N) F(N-1) fib(N) fib(N-1)] = [F(N-1) F(N-2) fib(N-1) fib(N-2)] * |1 0 0 0|
|1 0 1 1|
|1 0 1 0|
</pre><p></p>
<p>Now you can use matrix exponentiation to calculate <code>F(N)</code> till the desired N to solve the problem.</p>
<h3>II. F(N) = 2*F(N-1) + F(N-2) - 2*F(N-3) - F(N-4)</h3>
<p>Similar to (I) you can construct a 4x4 matrix and use matrix exponentiation.</p>
<p>4x4 matrix and its exponentiation leads to slightly larger constants and needs several micro optimizations to stay within the time limit. Thus, a better approach is to not need to do matrix exponentiation over 4x4 matrices at all, as outlined in (III) below.</p>
<h3>III. 5*F(N) = (n - 1)*fib(N + 1) + (n + 1)*fib(N - 1)</h3>
<p>This elegant result is derived in <a href="http://www.fq.math.ca/Scanned/15-2/hoggatt1.pdf">this paper</a>. Note that they assume fib[0] as 0 and fib[1] as 1.</p>
<p>Using the above result we can say that we need to find<br>
∑<sub><code>k = 1 to (N-1)</code></sub><code>fib(k+1) * [fib(N-k + 2) + fib(N-k + 3)]</code><br>
or ∑<sub><code>k = 1 to (N-1)</code></sub><code>fib(k+1) * fib(N-k + 4)</code></p>
<p>We can rewrite the above as<br>
<code>F(N+5) - fib(0)*fib(N+5) - fib(1)*fib(N+4) - fib(N+1)*fib(4) - fib(N+2)*fib(3) - fib(N+3)*fib(2) - fib(N+4)*fib(1) - fib(N+5)*fib(0)</code><br>
<code>= F(N+5) - 2*fib(N+4) - fib(N+3) - 2*fib(N+2) - 3*fib(N+1)</code></p>
<p>A fibonacci number can be calculated by doing matrix exponentiation of a <code>2x2</code> matrix, which is very fast. We cal find fib(N+1) and fib(N) through one exponentiation of the matrix representation of fibonacci numbers and calculate fib(N+2), fib(N+3), fib(N+4), fib(N+5) and fib(N+6) from them.</p>
<p>You may notice that calculating F(N) requires you to divide an integer by 5. Since we maintain modulo all along to avoid overflows, we must calculate the division modulo 1000000007 as well.</p>
<p>This can be accomplished by finding the <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">modular multiplicative inverse</a> of 5, modulo 1000000007.</p>
<h1>SETTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/September/Setter/CHEFWD.cpp">here</a></p>
<h1>TESTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/September/Tester/CHEFWD.c">here</a></p>gamabuntaTue, 11 Sep 2012 15:23:13 +0530https://discuss.codechef.com/questions/2265/chefwd-editorialmathssep12fibonaccieditorialmatrix-expoTLE in Family of Recurrenceshttps://discuss.codechef.com/questions/51340/tle-in-family-of-recurrences<p>Here is the <a href="http://www.codechef.com/problems/KAN13D">problem</a>.</p>
<p>I have implemented matrix multiplication to solve the recurrence relation. the order of the solution should be O(m^3 * log(n) * T) which is approximately 32 * 10^6 * 20 = 64 * 10^7, which should be done in 1 sec.The time limit of the problem is 15 sec, still I am getting TLE.</p>
<p>Please Help, here is <a href="http://www.codechef.com/viewsolution/4856788">my solution</a></p>the65bitSat, 20 Sep 2014 04:07:27 +0530https://discuss.codechef.com/questions/51340/tle-in-family-of-recurrencesrecurrencematrix-expoMatrix Expohttps://discuss.codechef.com/questions/63436/matrix-expo<p>a(0) = -1<br>
a(1) = 1<br>
a(n) = 2<em>a(n-1) + 3</em>a(n-2) + pow (3, n)</p>
<p>Solving using matrix exponentiation</p>
<p>How to calculate the initial matrices</p>nidhi1234Sat, 31 Jan 2015 13:21:02 +0530https://discuss.codechef.com/questions/63436/matrix-expomatrix-expoLogarithmic solution for linear recursive equationhttps://discuss.codechef.com/questions/65988/logarithmic-solution-for-linear-recursive-equation<p><a href="http://www.codechef.com/viewsolution/547362">http://www.codechef.com/viewsolution/547362</a>
This is a solution for the problem "The Great Wall of Byteland" http://www.codechef.com/problems/BWALL which is basically solving the linear recursive equation. I have seen normal solution which in involves creation of k^2 transformation matrix and have complexity K^3*log(n) but this looks differnet. Can someone explain how it works and what is its complexity.</p>begin_hsSat, 14 Mar 2015 23:13:45 +0530https://discuss.codechef.com/questions/65988/logarithmic-solution-for-linear-recursive-equationrecursionfibonaccimatrix-exposeries vs wallhttps://discuss.codechef.com/questions/68042/series-vs-wall<p>can anyone tell me how to solve this using matrix multiplication method..<a href="http://www.codechef.com/DTCT2015/problems/WSERIES/">http://www.codechef.com/DTCT2015/problems/WSERIES/</a>
...or what is the matrix relation this user used..<a href="http://www.codechef.com/viewsolution/6785175">http://www.codechef.com/viewsolution/6785175</a></p>ankit3193Sat, 18 Apr 2015 10:16:54 +0530https://discuss.codechef.com/questions/68042/series-vs-wallrecursionmatrix-expoTAPALIN - Editorialhttps://discuss.codechef.com/questions/7695/tapalin-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/TAPALIN">Practice</a><br>
<a href="http://www.codechef.com/COOK32/problems/TAPALIN">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES</h1>
<p>Simple Math, Matrix Exponentiation</p>
<h1>PROBLEM</h1>
<p>Find the number of palindromic strings that can be made of length <b>N</b>, or less.</p>
<h1>QUICK EXPLANATION</h1>
<p>We can fix the first <b>ciel(N/2)</b> characters of the string as we want, and the rest of the string is simply forced.</p>
<p>Also, each string we get by fixing the first <b>ciel(N/2)</b> characters is a unique palindromic string.</p>
<p>Thus, we can find the number of palindromic strings of each length</p>
<pre>F(n) = 26<sup>ceil(n/2)</sup></pre>
<p>Now, we need to find the summation of this result for all <b>n</b> from <b>1 to N</b> to find all the palindromic strings of length <b>N</b>, or less.</p>
<pre>SUMMA( F(n), 1 ≤ n ≤ N )
= 2*SUMMA( 26<sup>n</sup>, 1 ≤ n ≤ ceil(N/2) ),
for even N
2*SUMMA( 26<sup>n</sup>, 1 ≤ n ≤ floor(N/2) )
+ 26<sup>ceil(N/2)</sup>
for odd N
</pre>
<p>We know that we can find <b>a<sup>b</sup></b> for a large <b>b</b> by <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">repeated squaring</a>. The problem now reduces to calculating the following</p>
<pre>S(n) = SUMMA( 26<sup>n</sup>, 1 ≤ n ≤ T )</pre>
<h1>EXPLANATION</h1>
<p>There are two ways to find the result.</p>
<p><b>METHOD 1: Matrix Exponentiation</b></p>
<pre>S(n) = 26, for n = 1
= 26*S(n-1) + 26
</pre>
<p>We can build the matrix equation as below</p>
<pre>| S(n+1) | = | 26 26 | * | S(n) |
| 1 | | 0 1 | | 1 |
</pre>
<p>Thus, to find the result, we can calculate</p>
<pre>| 26 26 |<sup>T</sup>
| 0 1 |
</pre>
<p>By repeated squaring of matrices. The results need to be found <b>modulo 1000000007</b>. Since all calculations are <b>sum</b> or <b>product</b> only, the drill should be straightforward.</p>
<p><b>METHOD 2: Sum of Geometric Progression</b></p>
<pre>S(T) = 26*(26<sup>T</sup> - 1) / 25
</pre>
<p>Calculating the numerator modulo 1000000007 is pretty straight forward. We use repeated squaring for the exponent part.</p>
<p>But, to the uninitiated it might be confusing as to why can we get away with calculating the residue of the numerator considering we are yet to divide it by 25.</p>
<p>Here, we apply the concept of <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">modular arithmetic inverses</a>. These are well defined for <b>residues modulo primes</b>. 1000000007 happens to be a prime (and is often the reason it is chosen in problems by several authors). The modular arithmetic inverse of <b>25, modulo 1000000007</b> is</p>
<pre>25<sup>1000000005</sup></pre>
<p>We arrive at this result by virtue of <a href="http://en.wikipedia.org/wiki/Fermat's_little_theorem">Fermat's Little Theorem</a>. Since</p>
<pre>25<sup>1000000006</sup> = 1, modulo 1000000007
25 * 25<sup>1000000005</sup> = 1, modulo 1000000007
Thus,
25<sup>1000000005</sup> = 25<sup>-1</sup>, modulo 1000000007
</pre>
<p>Now, by using repeated squaring, we can find the modular inverse of <b>25</b> and multiply it to the numerator to find our answer.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/COOK32/Setter/TAPALIN.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/COOK32/Tester/TAPALIN.cpp">here</a>.</p>gamabuntaMon, 25 Mar 2013 00:12:29 +0530https://discuss.codechef.com/questions/7695/tapalin-editorialcook32modulosimplesimple-mathmatrix-expoeditorialFIBEQN - Editorialhttps://discuss.codechef.com/questions/80605/fibeqn-editorial<h1>FIBEQN Editorial by Satwant Rana</h1>
<p>The problem asks us to calculate $\sum_{i = 0}^n{F_i\ k^i}$, and time limit suggests we need to do it in $O(log\ N)$ time.</p>
<p>The model solution makes use of the fact that $F_i = \frac{\phi^i - \psi^i}{\phi-\psi}$, where $\phi = \frac{1 + \sqrt5}{2}$ and $\psi = \frac{1 - \sqrt5}{2}$. Leveraging this fact we can perform computations in $\mathbb Z[\sqrt5]$.</p>
<p>So the problem asks us to calculate $\sum_{i = 0}^n{\frac{\phi^i - \psi^i}{\phi-\psi}\ k^i} = \frac{\frac{(\phi\ k)^i - 1}{\phi - 1} - \frac{(\psi\ k)^i - 1}{\psi - 1}}{\phi - \psi}$. This can be done in $O(log N)$ time with logarithmic exponentiation in $\mathbb Z[\sqrt5]$.</p>
<p><a href="http://pastebin.com/wws7hGdB">Setter's Solution</a></p>harrypotter192Fri, 01 Apr 2016 00:19:06 +0530https://discuss.codechef.com/questions/80605/fibeqn-editorialadvanced-mathipc15p3bfibonaccieditorialmatrix-expoHelp for Power Sumshttps://discuss.codechef.com/questions/86109/help-for-power-sums<p>Since the editorial is taking too long I would like to know if anyone could explain the solution for the large test case of <a href="https://www.codechef.com/OCT16/problems/POWSUMS">powsums</a>.</p>
<p>For the first test cases I used matrix exponentiation based on the recurrence relations of <a href="https://en.wikipedia.org/wiki/Newton's_identities">Newton's identities</a>. This solution worked on <strong>O(n^2)</strong> per query but required expensive pre calculation of <strong>O(n^3)</strong> (x30) step per test case and of course this would be too large to pass the larger test cases. I even thought of using a faster multiplication algorithm but it seemed more like an optimization and not really the intended solution.</p>
<p>I thought of 2 other approaches:</p>
<p><strong>1</strong> - Computing the eigen decomposition so I could reduce the time complexity from cubic to quadratic.</p>
<p><strong>2</strong> - Finding the roots of the polynomials so on each query I could compute the sums of powers directly.</p>
<p>But I failed, the articles on eigendecomposition are still hard to digest for me and had no success of finding/calculating the roots of the polynomials. The best I could do was to use Fermat's little theorem to reduce the range of <strong>xi</strong> from <strong>10e18</strong> to <strong>10e9</strong>.</p>junior94Mon, 17 Oct 2016 23:27:40 +0530https://discuss.codechef.com/questions/86109/help-for-power-sumsrecurrencepowsumsmatrix-expoSEQAGAIN Sequencehttps://discuss.codechef.com/questions/86492/seqagain-sequence<p>how to solve this <a href="http://www.spoj.com/problems/SEQAGAIN/">Problem</a>. </p>
<p><img alt="Here is the problem" src="https://discuss.codechef.com/upfiles/seqagain_1.png"></p>
<p>since n can be of the order 10^18, can it really be solved using just memoization(i don't think so) ? can this problem be solved using matrix exponentiation, but the recurrence is not linear. Help. </p>
<p>I came up with <a href="http://ideone.com/sQfhNa">THIS CODE</a>, can anyone point out why it is giving wrong answer ?</p>ashwanigautamMon, 24 Oct 2016 17:14:01 +0530https://discuss.codechef.com/questions/86492/seqagain-sequencematrix-expoBIKE - Editorialhttps://discuss.codechef.com/questions/87391/bike-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/BIKE">Practice</a><br>
<a href="http://www.codechef.com/NOV16/problems/BIKE">Contest</a></p>
<h1>DIFFICULTY:</h1>
<p>HARD</p>
<h1>PREREQUISITES:</h1>
<p>math, matrix expontiation, polynomial multiplication, lagrange polynomial</p>
<h1>PROBLEM:</h1>
<p>Given a directed graph of <strong>N</strong> vertices and integer <strong>T</strong>, each edge has two types of costs <strong>F<sub>i</sub></strong> and <strong>R<sub>i</sub></strong>, for each <strong>i</strong>, <strong>j</strong>, <strong>k</strong> count the number of paths of length <strong>T</strong> which starts at vertex <strong>i</strong> and end at same vertex, and the total cost of first type is <strong>j</strong> (modulo <strong>N</strong>) and the total cost of the second type is <strong>k</strong> (modulo <strong>N</strong>-1)</p>
<h1>SHORT EXPLANATION</h1>
<p>let's first find a way to mix both edge costs into a single cost in range <strong>0</strong> ... <strong>n * (n-1)-1</strong> then we use matrix exponentiation where each cell is a polynomial of degree <strong>n * (n-1)-1</strong>, the coefficient <strong>x<sup>i</sup></strong> of polynomial in cell in <strong>j</strong>-th row and <strong>k</strong>-th column tells us the number of ways to go from vertex <strong>j</strong> to vertex <strong>k</strong> in a route of length <strong>i</strong> modulo <strong>n * (n-1)</strong></p>
<p>so let's create matrix <strong>A</strong> of size <strong>N*N</strong> such that cell in <strong>j</strong>-th row and <strong>k</strong>-th column have polynomial equal to 0 if there's no edge from vertex <strong>j</strong> to vertex <strong>k</strong>, otherwise it is equal to <strong>x<sup>i</sup></strong> where <strong>i</strong> is the length of that edge</p>
<p>Now all we need is to compute <strong>A<sup>T</sup></strong> using matrix exponentiation then we are done, as you know fastest method to multiply two polynomials is <strong>O(m log m)</strong> where <strong>m</strong> is the degree of the biggest polynomial but this will be slow so we need to store polynomials in interpolation form of <strong>N * (N-1)</strong> values in a way that support circular convolution</p>
<h1>EXPLANATION</h1>
<h2>Changing double costs of an edge into single cost</h2>
<p>first thing to do is to find a way to change from double costs into a single cost <strong>L<sub>i</sub></strong>, this cost should satisfy <strong>L<sub>i</sub></strong> = <strong>F<sub>i</sub></strong> (mod <strong>N</strong>) and <strong>L<sub>i</sub></strong> = <strong>R<sub>i</sub></strong> (mod <strong>N-1</strong>), and it should be in range [0,N*(N-1)-1], this value <strong>L<sub>i</sub></strong> always exists and unique in that range since <strong>N-1</strong> and <strong>N</strong> are coprimes, to find this value:</p>
<p>since <strong>L<sub>i</sub></strong> = <strong>F<sub>i</sub></strong> (mod <strong>N</strong>) then <strong>L<sub>i</sub></strong> should be of form <strong>K*N+F<sub>i</sub></strong>, let's substitute it in <strong>L<sub>i</sub></strong> = <strong>R<sub>i</sub></strong> (mod <strong>N-1</strong>) so we have </p>
<p><strong>K*N+F<sub>i</sub></strong> = <strong>R<sub>i</sub></strong> (mod <strong>N-1</strong>)</p>
<p><strong>K</strong> = <strong>R<sub>i</sub></strong>- <strong>F<sub>i</sub></strong> (mod <strong>N-1</strong>)</p>
<p>so <strong>K</strong> should be equal to (<strong>R<sub>i</sub></strong>- <strong>F<sub>i</sub></strong>) mod <strong>N-1</strong></p>
<h2>Transformation matrix</h2>
<p>Let's create a matrix <strong>A</strong> of <strong>N</strong> * <strong>N</strong> cells such that cell in <strong>j</strong>-th row and <strong>k</strong>-th column have polynomial equal to 0 if there's no edge from vertex <strong>j</strong> to vertex <strong>k</strong>, otherwise it is equal to <strong>x<sup>i</sup></strong> where <strong>i</strong> is the length of that edge.</p>
<p>now <strong>A<sup>T</sup></strong> will give us the information we need, cell <strong>i</strong>-th row and <strong>j</strong>-th column will give us a polynomial of degree <strong>N*(N-1)-1</strong> such that its coefficient of <strong>x<sup>k</sup></strong> will tell us the number of paths from vertex <strong>i</strong> to <strong>j</strong> of length <strong>k</strong> (modulo <strong>N * (N-1)</strong>)</p>
<p>how to compute <strong>A<sup>T</sup></strong>? if we used <strong>O(N^3)</strong> matrix multiplication algorithm and <strong>O(M log M)</strong> FFT polynomial multiplication algorithm (where <strong>M</strong> is degree of polynomial which is <strong>N * (N-1)</strong>), then we will have <strong>O(N^5 log N log T)</strong> solution which is so slow specially with the hight constant factor from FFT algorithm so we need a faster method.</p>
<h2>Faster multiplication method</h2>
<p>actually we can make polynomial multiplication faster if we store polynomials in other way than the set of coefficient values, a polynomial of degree <strong>N * (N-1)-1</strong> can be uniquely determined by interpolation of <strong>N * (N-1)</strong> points, usually it's fine to choose any <strong>N * (N-1)</strong> points but since in our case our polynomial multiplication should be circular (i.e. if exponent of some <strong>X</strong> became bigger or equal <strong>N * (N-1)</strong> then we should take the exponent modulo <strong>N * (N-1)</strong>)</p>
<p>for this reason we have to choose <strong>N * (N-1)</strong> points carefully, now let <strong>w</strong> be an integer such that <strong>w^(N * (N-1)) = 1 (mod 1163962801)</strong>, then in each cell of transformation matrix we store those <strong>N * (N-1)</strong> values</p>
<p><strong>P(w<sup>0</sup>), P(w<sup>1</sup>), P(w<sup>2</sup>), ... P(w<sup>N * (N-1)-1</sup>)</strong></p>
<p>where <strong>P</strong> is the polynomial in that cell, now to multiply two polynomials <strong>A</strong> and <strong>B</strong> we just calculate <strong>N * (N-1)</strong> new points which are</p>
<p><strong>A(w<sup>0</sup>) * B(w<sup>0</sup>), A(w<sup>1</sup>) * B(w<sup>1</sup>), A(w<sup>2</sup>) * B(w<sup>2</sup>), ... A(w<sup>N * (N-1)-1</sup>) * B(w<sup>N * (N-1)-1</sup>)</strong></p>
<p>and this is <strong>O(N * (N-1))</strong> instead of <strong>O(N * (N-1) log (N * (N-1)))</strong>, now we just need to restore coefficients of polynomials on the diagonal of <strong>A<sup>T</sup></strong>, which can be done using lagrange interpolation.</p>
<h2>Lagrange Interpolation</h2>
<p>say we have <strong>N</strong> points (<strong>X<sub>1</sub>,</strong>Y<sub>1</sub><strong>), (</strong>X<sub>2</sub>,<strong>Y<sub>2</sub></strong>) ... (<strong>X<sub>N</sub>,</strong>Y<sub>N</sub>**)</p>
<p>and we want to find a polynomial which passes through all these points, it can be done in the following way.</p>
<p>let <strong>L<sub>i</sub>(X)</strong> be polynomial such that it returns zero on all <strong>X<sub>j</sub></strong> except when <strong>i=j</strong> it returns non-zero value</p>
<p>it's easy to see that <strong>L<sub>i</sub>(X) = (X-X<sub>1</sub>)(X-X<sub>2</sub>) ... (X-X<sub>i-1</sub>)(X-X<sub>i+1</sub>)...(X-X<sub>N</sub>)</strong></p>
<p>now say <strong>P</strong> is the required polynomial then </p>
<p><strong>P(X) = Y<sub>1</sub> * L<sub>1</sub>(X) / L<sub>1</sub>(X<sub>1</sub>) + Y<sub>2</sub> * L<sub>2</sub>(X) / L<sub>2</sub>(X<sub>2</sub>) ... Y<sub>N</sub> * L<sub>N</sub>(X) / L<sub>N</sub>(X<sub>N</sub>)</strong></p>
<p>now we extract <strong>P(X)</strong> to get the desired coefficients</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/NOV16/Setter/BIKE.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/NOV16/Tester/BIKE.cpp">here</a>.</p>kingofnumbersSat, 12 Nov 2016 12:38:22 +0530https://discuss.codechef.com/questions/87391/bike-editorialhardmatrix-expobikeeditorialmathsnov16SEALCM - Editorialhttps://discuss.codechef.com/questions/61308/sealcm-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SEALCM">Practice</a> <br>
<a href="http://www.codechef.com/JAN15/problems/SEALCM">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sereja">Sergey Nagin</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a> </p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM-HARD</p>
<h1>PRE-REQUISITES:</h1>
<p><a href="http://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation">Solving Dynamic Programming with Matrix Expo</a></p>
<h1>PROBLEM:</h1>
<p>In this problem Sereja is interested in number of arrays <b>A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ M, A[i] - integer)</b>
such that least common multiple (<a href="http://en.wikipedia.org/wiki/Least_common_multiple"><b>LCM</b></a>) of all its elements is divisible by number <b>D</b>.
</p><p></p>
<p>
Please, find sum of answers to the problem with <b>D = L, D = L+1, ..., D = R</b>. As answer could be large, please output it modulo (10<sup>9</sup> + 7).
</p>
<h1>TECHNIQUE:</h1>
<p>I will suggest to specifically read the whole post given in pre-requisite if you are not aware about this technique. </p>
<p>Let there be <strong>K</strong> states, <strong>s<sub>1</sub>,s<sub>2</sub>...s<sub>K</sub></strong>. <br>
For each state <strong>s<sub>i</sub></strong> where <strong>i = 1 to K</strong> recurrence is defined as: <br>
<strong>f(n,s<sub>i</sub>) = sum {j=1 to K} c<sub>{i,j}</sub> f(n-1,s<sub>j</sub>)</strong>. <br>
We define a transition matrix <strong>M</strong> where <strong>M[i][j]=c<sub>{i,j}</sub></strong>. <br>
Let's consider <strong>M<sup>{N-1}</sup></strong>. Sum of all elements in row <strong>i</strong> will give us <strong>f(N,s<sub>i</sub>)</strong> assuming <strong>f(0,i)=0</strong> forall <strong>i</strong>.</p>
<h1>EXPLANATION:</h1>
<p>Let's solve for a single <strong>D</strong> first. Let's say <strong>D</strong> has prime factors <strong>p<sub>1</sub><sup>a1</sup>, p<sub>2</sub><sup>a2</sup> ... p<sub>K</sub><sup>aK</sup></strong>, where all <strong>p<sub>i</sub></strong> are unique. <br>
We form a simple dp of <strong>dp[n,mask]</strong>, which denotes the answer for <strong>N=n</strong> and <strong>D</strong>=product [p<sub>i</sub><sup>a_i</sup>], if <strong>i</strong>'th bit is set in <strong>mask</strong>. So, <strong>mask</strong> is a <strong>K</strong> bit number. <br>
A simple recurrence would be: </p>
<pre><code>&ret = dp[n,mask]
primes[] //prime factors of D.
count[] //count[i] denotes count of i'th prime in D
ret=0
for i = 0 to size(primes)-1:
for j = 1 to M:
//if j is kept at n'th index
//and keeping it satisfies the i'th set bit condition
//ie. count of primes[i] in j is greater than or equal to count[i]
if count_prime(primes[i] in j) >= count[i]
//set the i'th bit, add to current ret
ret += dp[n-1, mask|(1<<i)]
</code></pre>
<p>So, we can clearly see that our <strong>dp[n,x]</strong> is dependent on <strong>dp[n-1,y]</strong>, where <strong>x</strong> and <strong>y</strong> are two different masks/states. We can use matrix exponentiation here because in one state in our dp, answer for <strong>n</strong> is dependent on answer for <strong>n-1</strong> and the transition among other states is not dependent on <strong>n</strong>. </p>
<p>So, we form the transition matrix, where we set at <strong>transit[i][j]</strong>, the number of ways to reach mask <strong>j</strong> from mask <strong>i</strong> . Sum of all elements in <strong>(2<sup>K</sup>-1)</strong>'th (all bits of <strong>D</strong> are set) row of <strong>N-1</strong>'th power of this transition matrix, will give us the answer, in accordance with the technique explained above. Try to prove how this works. </p>
<p>So, complexity for single <strong>D</strong> is <strong>O(log N * (2<sup>K*3</sup>))</strong>. Note matrix multiplication of sizes P*P takes O(P<sup>3</sup>).
And, maximum K is until 2<em>3</em>5<em>7</em>11*13... is smaller than 1000(since D<1000). So, max K is 4.
Total complexity for single <strong>D</strong> is <strong>O(log N * 2<sup>12</sup>)</strong>.</p>
<p>Doing it for 1000 such values of <strong>D</strong> will take <strong>O(log N * 2<sup>22</sup>)</strong> worst case. Note it will be really lower than that because of variation in <strong>K</strong>.</p>
<h1>SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/JAN15/Setter/SEALCM.cpp">Setter's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/JAN15/Tester/SEALCM.cpp">Tester's solution</a> </p>darkshadowsMon, 12 Jan 2015 15:08:02 +0530https://discuss.codechef.com/questions/61308/sealcm-editorialsealcmjan15medium-hardmatrix-expodynamic-programmingeditorialGrid Painting- Editorialhttps://discuss.codechef.com/questions/54044/grid-painting-editorial<p><strong>Problem Link : </strong>
<a href="http://www.codechef.com/WPC1401/problems/IITK1P09">Contest</a>
<a href="http://www.codechef.com/problems/IITK1P09">Practice</a></p>
<p><strong>Difficulty : </strong> Hard</p>
<p><strong>Pre-requisites : </strong> DP, Matrix exponentiation, k-length paths in a graph</p>
<p><strong>Solution : </strong>
</p><p>
</p><ol>
<li>When X = 1, there is no interdependency between two different rows. All you need to do is find the number of solutions for one row, and raise it to the total number of rows. <br>
For the number of solutions of a single row, it is a simple linear dp. <br>
<br>For, 1 ≤ i ≤ m, 1 ≤ j < y, dp[i][j] = number of rows of length i with exactly j repeated squares of black or white appended in the end.<br>
<br><br><strong>Base case</strong> : <br>dp<a href="http://www.codechef.com/WPC1401/problems/IITK1P09">1</a> = 2 <br>
<br><strong>Update</strong> :<br>For i > 1, <ul><li>If j = 1, the colour of the ith block is not the same as that of the (i-1)th block.
<br>So, we have dp<a href="http://www.codechef.com/WPC1401/problems/IITK1P09">i</a> = <span>Σ</span>dp[i-1][k], for 1 ≤ k < (min(i+1,y))
</li><li>If j > 1, then the colour we consider now must be the previous colour. So, dp[i][j] = dp[i-1][j-1].
</li></ul>
<br>Finally, the answer is (<span>Σ</span>dp[m][k], for 1 ≤ k < y)^n
</li>
<br>
<li>
The case for X=2 is more interesting. Here, there is interdependency between two consecutive rows. <p>The first thing that comes to mind is to create a dp with two parameters - the index of the current row, and the configuration of the previous row as a bitmask.
<br> Now, evaluating the dp for every state requires 2^M steps. And the number of states is 2^M x N. So, overall complexity is O(2^(2M)<em>N) which is infeasible.</em></p><em>
</em><p><em> There is a standard way of resolving this issue using matrix exponentiation. What we do is look at every possible configuration of a row as a node in a graph. We connect two edges of a graph if two rows can occur consecutively, that is that they do not form a single colour box of size X x Y.
<br> Constructing the graph is done via a single (2^M)</em>(2^M) loop that checks every pair of vertices if they can be connected in M^3 time (simple brute force algorithm). The graph is stored as an adjacency matrix.<br>
<br> Now, we need the number of N-1 length walks of this graph. This is a problem solved by taking the adjacency matrix A, evaluating A^(N-1), and adding all the entries of the obtained matrix.<br>
<br> We perform matrix exponentiation in log N steps, where each matrix multiplication takes (2^M)^3 = 2^21 time.
</p></li>
<li>
What happens if we apply the same solution as above for the next case of X=3?
<p> Again we can create vertices of the graph as the configuration of two consecutive rows of the grid. <br>Two vertices are joined if and only if the second row of the first vertex matches the first row of the second vertex, and the 3 rows are compatible to the condition that no X x Y block is uni-colour.
<br> Note that now the adjacency matrix is 2^(2M) x 2^(2M), and multiplication will require 2^(6M) = 2^30 time which will get TLE'd.
</p><p> Interestingly, observe that although the matrix is 2^(2M) x 2^(2M), it is very sparse, and only 2^M entries may be filled in every row.
<br> We store this matrix as an adjacency list, and multiply by using the naive algorithm, looking at only these (non-zero) entries. The multiplication now takes 2^(5M) = 2^25 time.
<br> However, only the initial matrix A is sparse, and A^2, A^4... may not be. Thus matrix exponentiation will not work in log time.
<br> <br>This is why N was given to be small! We can still appply the naive algorithm, and iteratively pre-multiply A (which is always sparse) to the current matrix (which may not be sparse) to obtain the final answer.
<br> This is a total of N steps, giving the complexity as O(N*(2^(5M))).
</p>
</li>
</ol>
<p></p><p></p>
<p><strong>Setter's code : </strong> <a href="http://www.codechef.com/viewsolution/4942842">code</a></p>cg11Sat, 25 Oct 2014 20:38:48 +0530https://discuss.codechef.com/questions/54044/grid-painting-editorialwpc1iitk1p09dynamic-programmingpaths-in-graphhardmatrix-expoeditorialGrid painting - Editorialhttps://discuss.codechef.com/questions/52119/grid-painting-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/WPC1401/problems/IITK1P09">contest</a> <br>
<a href="http://www.codechef.com/problems/IITK1P09">practice</a></p>
<p><strong>Difficulty</strong> : Hard</p>
<p><strong>Pre-requisites</strong> : Matrix exponentiation, dp</p>
<p><strong>Solution</strong> :</p>
<ul>
<li>When X = 1, You can do a simple dp. For optimizing that dp, you need to use matrix exponentiation. </li>
<li>When X = 2, Idea is similar, but this time rows and coloumns of matrix will be larger.</li>
<li>When X = 3, You can notice that matrix created will be sparse, You can use this observation very well. As N is very small. Assume you want to compute A^n where n is small. Note that we will
keep multiplying A by A, then A^2 by A, then A^3 by A, In the process we are always doing a multiplication by a sparse matrix.<br>
You can also do a dp here too. You don't need matrix exponentiation too.</li>
</ul>
<p><strong>Setter's solution</strong>: <a href="http://www.codechef.com/viewsolution/4942842">link</a></p>dpraveenWed, 01 Oct 2014 20:06:28 +0530https://discuss.codechef.com/questions/52119/grid-painting-editorialwpc1iitk1p09dynamic-programmingiitkmatrix-expowpc1401editorialwpcPOWSUMS - Editorialhttps://discuss.codechef.com/questions/86250/powsums-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/POWSUMS">Practice</a><br>
<a href="http://www.codechef.com/OCT16/problems/POWSUMS">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>medium-hard</p>
<h1>PREREQUISITES</h1>
<p>dp, matrix exponentiation, newton's identities, elementary symmetric polynomials</p>
<h1>PROBLEM</h1>
<p>Let $f(x) = {a_1}^x + {a_2}^x + \dots + {a_n}^x \pmod {10^9 + 7}$, where $a_1, a_2, \dots, a_n$ are integers. You don't know $a_1, a_2, \dots, a_n$. Instead you have the values of $f(1), f(2), \dots, f(n)$. You are to find $f(x)$ for some given $x$. </p>
<h1>QUICK EXPLANATION</h1>
<h1>EXPLANATION</h1>
<h2>Take small Examples</h2>
<p>Let us take small examples to understand definition of $f(x)$. </p>
<p>Let $n = 1$, $f(x) = {a_1}^x$. i.e. $f(1) = a_1$.<br>
We are given value of $f(1)$, so know value of $a_1$. So we know that function $f(x)$. Now, we can evaluate $f$ for any $x$.</p>
<p>Let $n = 2$. $f(x) = {a_1}^x + {a_2}^x$.
$$f(1) = a_1 + a_2$$
$$f(2) = {a_1}^2 + {a_2}^2$$
$f(1)$ and $f(2)$ are known values. We want to evaluate $f(x)$ for any $x$. </p>
<p>$$\text{Write } {a_1}^2 + {a_2}^2 = {(a_1 + a_2)}^2 - 2 \cdot a_1 \cdot a_2$$
$$f(2) = f(1)^2 - 2 \cdot a_1 \cdot a_2$$
$$a_1 \cdot a_2 = \frac{f(2) - f(1)^2} {2} $$</p>
<p>We know value of $a_1 \cdot a_2$ and $a_1 + a_2 = f(1)$. Using this information, we can find values of $a_1, a_2$.</p>
<h2>Elementary symmetric polynomials</h2>
<p>Elementary symmetric polynomials are one of the important constructs in mathematics, any symmetric polynomial can be represented as a polynomial in elementary symmetric polynomials. In other words, any symmetric polynomial can be represented by an expression involving only additions and multiplications of elementary symmetric polynomials. There is one elementary symmetric polynomial of degree $d$ in $n$ variables ($d \leq n)$, which is formed by adding together products of $d$ distinct variables. For brevity, we will refer elementary symmetric polynomial of degree $d$ in $n$ variables as $ESP(n, d)$.</p>
<p>For example, let us consider only two variables i.e. $n = 2$, $a_1$ and $a_2$. <br>
$$ESP(2, 0) = 1$$
$$ESP(2, 1) = a_1 + a_2$$
$$ESP(2, 2) = a_1 a_2$$</p>
<p>Now let us consider only two variables $n = 3$, $a_1, a_2$ and $a_3$. </p>
<p>$$ESP(3, 0) = 1$$
$$ESP(3, 1) = a_1 + a_2 + a_3$$
$$ESP(3, 2) = a_1 a_2 + a_2 a_3$$
$$ESP(3, 3) = a_1 a_2 a_3$$</p>
<p>A more complex example
$$ESP(4, 3) = a_1 \, a_2 \, a_3 + a_1 \, a_2 \, a_4 + a_1 \, a_3 \, a_4 + a_2 \, a_3 \, a_4$$</p>
<p>In other words, each term will be sum of product of all $d$ sized subset of distinct variables. In general, there will be total $\binom{n}{d}$ terms in it.</p>
<p>Any symmetric polynomial can be represented in terms of ESP's. Here are some examples.</p>
<p>$$a_1 + a_2 = ESP(2, 1)$$</p>
<p>$${a_1}^2 + {a_2}^2 = {(a_1 + a_2)}^2 - 2 \cdot a_1 \cdot a_2$$
$${a_1}^2 + {a_2}^2 = {ESP(2, 1)}^2 - 2 \, ESP(2, 2)$$</p>
<h2>Expressing EPSs in terms of power sums</h2>
<p>Let us denote $ESP(n, k)$ as $e_k$. </p>
<p>We see</p>
<p>$$e_0 = f(0)$$
$$e_1 = f(1)$$
$$e_2 = \frac{e_1 \, f(1) - e_0 \, f(2)}{2}$$
$$e_3 = \frac{e_2 \, f(1) - e_1 \, f(2) + e_0 \, f(3)}{3}$$
$$e_4 = \frac{e_3 \, f(1) - e_2 \, f(2) + e_1 \, f(3) - e_0 \, f(4)}{4}$$
In general,
$$e_k = \frac{e_{k - 1} \, f(1) - e_{k - 2} \, f(2) + \dots \pm e_0 \, f(k)}{k}$$</p>
<p>Using these relations, we can obtain values of $e_0, e_1, \dots e_n$ by the values of $f(1), f(2), \dots, f(n)$ in total $\mathcal{O}(n^2)$ time. </p>
<h2>Expressing power sums in terms of ESPS</h2>
<p>Rewriting the above equations used in previous section, we get</p>
<p>$$f(0) = e_0$$
$$f(1) = e_1$$
$$f(2) = e_1 \, f(1) - 2 \, e_2 \, f(0)$$
$$f(3) = e_1 \, f(2) - e_2 \, f(1) + 3 \, e_3 \, f(0)$$
$$f(4) = e_1 \, f(3) - e_2 \, f(2) + e_3 \, f(1) - 4 \, e_4 \, f(0)$$</p>
<p>In general,</p>
<p>$$f(n) = e_1 \, f(n - 1) - e_{2} \, f(n - 2) + \dots \pm n \, e_n \, f(0)$$</p>
<p>As we know that $e_i$ for $i > n$ will be zero.</p>
<p>So, we get
$$f(n + 1) = e_1 \, f(n) - e_{2} \, f(n - 1) + \dots \pm (n + 1) \, e_{n + 1} \, f(0)$$
As $e_{n + 1} = 0$.
$$f(n + 1) = e_1 \, f(n) - e_{2} \, f(n - 1) + \dots \pm (n) \, e_{n} \, f(1)$$
We see that it has only $n$ terms.</p>
<p>In general $f(X)$ for even $X > n$ will contain $n$ terms in its representation of ESPs.</p>
<h2>Solving recurrence relations</h2>
<p>Now, we see that $f(X)$ for $X > n$ can be represented as a recurrence relation of $n$ terms. Also coefficients in this recurrence relation are constant or linearly related with $i$. So the recurrence relation is linear.</p>
<p><strong>Direct matrix multiplication for each query</strong><br>
Using the direct matrix exponentation, we will get $\mathcal{O}(n^3 \, log X)$ time complexity for a single query of $f(X)$. There are $Q$ queries, so, the total time will be $\mathcal{O}(Q \, n^3 \, log X)$. This can solve up to three subtasks.</p>
<p><strong>Slightly faster solution</strong> <br>
We can precompute $M, M^2, M^4, M^8, M^{16}, \dots, M^{2^p}$, such that p is largest number satisfying $2^p \leq 10^{18}$. </p>
<p>As mulitplying a matrix with a vector takes $\mathcal{O}(n^2)$ time. The query $f(X)$ can be answered in at most $log(X)$ multiplications of the precomputed matrices and a constant vector, to answer each query in $\mathcal{O}(n^2) log X$ time.</p>
<p>Overall time taken will be dominated by precomputing as number of queries are small. So, we get $\mathcal{O}(n^3 \, log X)$ time.</p>
<p>Let us take a small example to describe this in detail. Let us take the simplest example of finding fibonacci number.</p>
<p>$$f(0) = 0$$
$$f(1) = 1$$
$$f(n) = f(n - 1) + f(n - 2)$$</p>
<p>$$</p>
<p>\begin{pmatrix}
f(1) \\
f(0)
\end{pmatrix}</p>
<p>=</p>
<p>\begin{pmatrix}
1 \\
0
\end{pmatrix}</p>
<p>$$</p>
<p>$$
\begin{pmatrix}
f(n) \\
f(n - 1)
\end{pmatrix}</p>
<p>=</p>
<p>\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}</p>
<p>.</p>
<p>\begin{pmatrix}
f(n - 1) \\
f(n - 2)
\end{pmatrix}
$$</p>
<p>$$
\begin{pmatrix}
f(n) \\
f(n - 1)
\end{pmatrix}</p>
<p>=</p>
<p>{
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
}^{n - 1}</p>
<p>.</p>
<p>\begin{pmatrix}
1 \\
1
\end{pmatrix}
$$</p>
<p>Let </p>
<p>$$
M</p>
<p>=</p>
<p>{
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
}
$$</p>
<p>and the vector $v$ be </p>
<p>$$
v</p>
<p>=</p>
<p>{
\begin{pmatrix}
1\\
0
\end{pmatrix}
}
$$</p>
<p>Assume we computed, M, M^2, M^4, M^8 etc.</p>
<p>We want to compute f(8). As we know that $f(8) = M^7 v$. We can write M^7 as $M^1 * M^2 * M^4$.</p>
<p>$f(8) = M^1 * M^2 * M^4 * v$</p>
<p>Multiply the matrices in the <strong>order from right to left</strong> instead of left to right. So, each time we multiply the matrix with a vector. So, we do total 3 multiplications of matrix with vector when we go from right to left. If we go from left to right, we need to 2 multiplication of matrices and one multiplication with constant vector.</p>
<h2>Subtask 4</h2>
<p>We need to optimize the pre-computation step. Using Cayley Hamilton theorem, we can find $f(X)$ in $\mathcal{O}(n^2 log X)$ time. A nice explanation of this can be found <a href="https://discuss.codechef.com/questions/49614/linear-recurrence-using-cayley-hamilton-theorem">here</a>. This can optimize the pre-computation step to $\mathcal{O}(n^2 \, log X \, log 10^{18})$.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/OCT16/Setter/POWSUMS.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/OCT16/Tester/POWSUMS.cpp">here</a>.</p>dpraveenThu, 20 Oct 2016 06:46:00 +0530https://discuss.codechef.com/questions/86250/powsums-editorialpowsumsdynamic-programmingmedium-hardmatrix-expooct16editorialACM14KN2 - Editorialhttps://discuss.codechef.com/questions/56971/acm14kn2-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ACM14KN2">Practice</a><br>
<a href="http://www.codechef.com/ACMKAN14/problems/ACM14KN2">Contest</a></p>
<p><strong>Author:</strong> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic Programming, Fast Matrix Power</p>
<h1>PROBLEM:</h1>
<p>You are asked to divide N slots to 3 people, A, B, and C. The number of slots allocated to A should be a multiple of k. There should be no consecutive slots for B. C should have at least one slot.</p>
<h1>EXPLANATION:</h1>
<h2>General Idea</h2>
<p>As k is small, we can use the following states to record the number of plans.</p>
<p>F[i][a][b][c] stands for the number of plans of allocated i slots to A, B, and C, where the number of slots of A mod k is a; b is a Boolean variable indicating whether B has the i-th slot; c is also a Boolean variable indicating whether C already has a slot.</p>
<p>Transitions are nearly obvious by considering the owner of (i+1)-th slot.</p>
<p>However, this bruteforce dynamic programming leads to an O(Nk) running time.</p>
<p>It is worth noting that the transitions are all between F[i][*] and F[i+1][*], and the operations are all multiplying come constants and summations. Therefore, we can get some intuitions to apply the fast matrix power to speed up the transitions. Finally, we get an algorithm with O(k^3 logN).</p>
<p>See more details in the author’s and tester’s solution for the fast matrix power algorithm if you are not familiar with that.</p>
<h2>Corner Case</h2>
<p>When k = 0, the number of slots allocated to A should be 0.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Solutions will be available soon.</p>shangjingboMon, 01 Dec 2014 09:03:50 +0530https://discuss.codechef.com/questions/56971/acm14kn2-editorialacm14kn2dynamic-programmingacmkan14matrix-expoeasy-mediumeditorialSEAPERM3 - Editorialhttps://discuss.codechef.com/questions/87190/seaperm3-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SEAPERM3">Practice</a><br>
<a href="http://www.codechef.com/NOV16/problems/SEAPERM3">Contest</a></p>
<h1>DIFFICULTY:</h1>
<p>HARD</p>
<h1>PREREQUISITES:</h1>
<p>dynamic programming, matrix expontiation</p>
<h1>PROBLEM:</h1>
<p>Given two arrays <strong>X</strong> and <strong>V</strong> of length <strong>M</strong> and an integer <strong>N</strong>, count the number of permutations <strong>P</strong> of length <strong>N</strong> which satisfy all the following: </p>
<ul>
<li>There exist at least one pair <strong>(i,j)</strong> such that <strong>P<sub>i</sub> > j</strong> and <strong>P<sub>j</sub> > i</strong></li>
<li>for all <strong>j</strong> between 1 and <strong>M</strong> we have <strong>P<sub>X<sub>j</sub></sub> = V<sub>j</sub></strong></li>
</ul>
<h1>EXPLANATION:</h1>
<p>Let's call a pair <strong>(i,j)</strong> good if it satisfy <strong>P<sub>i</sub> > j</strong> and <strong>P<sub>j</sub> > i</strong>, the problem asks us to count the number of permutations having at least one good pair and also satisfying second condition (i.e. for all <strong>j</strong> between 1 and <strong>M</strong> we have <strong>P<sub>X<sub>j</sub></sub> = V<sub>j</sub></strong>).</p>
<p>instead of counting the number of permutations having at least one good pair we count the number of permutation having no good pairs then we subtract it from total number of permutations satisfying second condition.</p>
<h2>Observation 1: All permutations which don't have good pairs must satify <strong>P<sub>i</sub> ≤ i+2</strong> for all <strong>i</strong> between 1 and <strong>N</strong></h2>
<p>proof: Let's assume <strong>P<sub>i</sub> = i+3</strong> or bigger then all <strong>P<sub>j</sub></strong> such that <strong>j < i+3</strong> must have value less than <strong>i</strong> in order to prevent having a bad pair, but there are <strong>i+1</strong> such elements to fill but only <strong>i</strong> different values available so this is impossible.</p>
<h2>Observation 2: if <strong>P<sub>i</sub> ≤ i+2</strong> for some permutation then only consecutive elements can be good pair in that permutation.</h2>
<p>proof: Let's say elements with indices <strong>i</strong> and <strong>j</strong> are bad <strong>i < j</strong> then <strong>j < P<sub>i</sub></strong> but we have <strong>P<sub>i</sub> ≤ i+2</strong> so <strong>i < j < i+2</strong> and that means <strong>j = i + 1</strong></p>
<h2>Special Case: arrays <strong>X</strong> and <strong>V</strong> are empty</h2>
<p>This is can be solved by dynamic programming, let <strong>F<sub>i,0</sub></strong> means the number of ways to fill first <strong>i</strong> elements of the permutation and the value of <strong>i</strong>-th element is <u>NOT</u> <strong>i+2</strong>, and <strong>F<sub>i,1</sub></strong> means the number of ways to fill first <strong>i</strong> elements of the permutation and the value of <strong>i</strong>-th element is <u>equal to</u> <strong>i+2</strong></p>
<p>now let's think of transactions clearly all values of <strong>F<sub>i</sub></strong> should be computed using only <strong>F<sub>i-1</sub></strong>, so let's think of four cases </p>
<ul>
<li>We want to set <strong>P<sub>i</sub> = i+2</strong> and <strong>P<sub>i-1</sub> = i-1+2</strong>: this will lead to have good pair so we should ignore this case.</li>
<li>We want to set <strong>P<sub>i</sub> = i+2</strong> and <strong>P<sub>i-1</sub> != i-1+2</strong>: so we have this transaction <strong>F<sub>i,1</sub> += F<sub>i-1,0</sub></strong></li>
<li>We want to set <strong>P<sub>i</sub> != i+2</strong> and <strong>P<sub>i-1</sub> != i-1+2</strong>: note that we have exactly two ways to pick a value for <strong>P<sub>i</sub></strong> so <strong>F<sub>i,0</sub> += 2 * F<sub>i-1,0</sub></strong></li>
<li>We want to set <strong>P<sub>i</sub> != i+2</strong> and <strong>P<sub>i-1</sub> = i-1+2</strong>: we have exactly one way to pick a value for <strong>P<sub>i</sub></strong>, because there are exactly 3 values between 1 and <strong>i+2</strong> not picked yet, one of them is <strong>i+2</strong>, and second one is <strong>i</strong> because if it was picked then <strong>(i-2,i-1)</strong> would be a good pair, and the last one is a value less than <strong>i</strong>, we don't want to pick <strong>i+2</strong> as we assumed <strong>P<sub>i</sub> != i+2</strong> from the beginning also we can't pick <strong>i</strong> otherwise <strong>(i-1,i)</strong> would be a good pair, so the only option left is the value which is less than <strong>i</strong>, that's why we have exactly one way to pick a value for <strong>P<sub>i</sub></strong>. so <strong>F<sub>i,0</sub> += F<sub>i-1,1</sub></strong></li>
</ul>
<p>so this will lead to <strong>O(N)</strong> solution which can be done in <strong>O(log n)</strong> using matrix exponentiation </p>
<h2>Full solution</h2>
<p>in case <strong>X</strong> and <strong>V</strong> were empty we could use matrix exponentiation immediately because transformation matrix is fixed for all indices <strong>i</strong>. however, in case <strong>X</strong> and <strong>V</strong> are not empty then transformation matrix is not the same for all positions because coefficients of the transactions discussed above can be different and they depend on arrays <strong>X</strong> and <strong>V</strong>, so we need to divide the indices of the array <strong>P</strong> into ranges such that each range have a the same transformation matrix, in order to do so we create new array <strong>Q</strong> having those values:</p>
<ul>
<li><strong>X<sub>i</sub>-2</strong>, <strong>X<sub>i</sub>-1</strong>, <strong>X<sub>i</sub></strong>, <strong>X<sub>i</sub>+1</strong> and <strong>X<sub>i</sub>+2</strong> for all <strong>i</strong> between 1 and <strong>M</strong></li>
<li><strong>V<sub>i</sub>-2</strong>, <strong>V<sub>i</sub>-1</strong>, <strong>V<sub>i</sub></strong>, <strong>V<sub>i</sub>+1</strong> and <strong>V<sub>i</sub>+2</strong> for all <strong>i</strong> between 1 and <strong>M</strong></li>
<li><strong>N-1</strong> and <strong>N</strong></li>
</ul>
<p>after that we remove duplications from <strong>Q</strong> then sort it in increasing order, now it's easy to see that transformation matrix on the range <strong>Q<sub>1</sub></strong>..<strong>Q<sub>2</sub></strong> is the same and also it's same for range <strong>Q<sub>2</sub></strong>..<strong>Q<sub>3</sub></strong> and so on.</p>
<p>so we can apply matrix expontiation on each range alone and we would have complexity <strong>O(K log N)</strong> where <strong>K</strong> is the size of array <strong>Q</strong>, but <strong>K</strong> is <strong>O(M)</strong> so overall complexity is <strong>O(M log N)</strong> but it has very large constant factor (i.e. 8 from matrix multiplication and 10 from the size of <strong>Q</strong>)</p>
<h2>Computing N factorial</h2>
<p>We need to compute <strong>N!</strong> because as we said before we count the number of not required permutations then subtract them from total number of permutation, so to compute <strong>N!</strong> we can pre-compute the factorial for each <strong>N</strong> multiple of 10<sup>7</sup> on our own machine then paste the answers in the source code, now computing <strong>N!</strong> for any <strong>N</strong> will not take more than 10<sup>7</sup> operations</p>
<h1>SETTER'S SOLUTION</h1>
<p>Will be uploaded soon.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/NOV16/Tester/SEAPERM3.cpp">here</a>.</p>kingofnumbersWed, 09 Nov 2016 02:50:57 +0530https://discuss.codechef.com/questions/87190/seaperm3-editorialseaperm3dynamic-programminghardmatrix-expoeditorialnov16How to solve dp with fast matrix exponentiation when matrix is not fixed?https://discuss.codechef.com/questions/71715/how-to-solve-dp-with-fast-matrix-exponentiation-when-matrix-is-not-fixed<p>I am trying to solve <a href="http://www.codechef.com/ACMKAN14/problems/ACM14KN2">www.codechef.com/ACMKAN14/problems/ACM14KN2</a>. It requires dp with fast matrix exponentiation but the matrix doesn't seem to be fixed. When k=0 the recurrence is F[n] = F[n-1] + F[n-2] but I can't figure out the complete solution. How can the matrix be generalized? </p>aaijmrtMon, 15 Jun 2015 21:59:38 +0530https://discuss.codechef.com/questions/71715/how-to-solve-dp-with-fast-matrix-exponentiation-when-matrix-is-not-fixeddynamic-programmingacm-icpcmatrix-expoLEPAPER - Editorialhttps://discuss.codechef.com/questions/3949/lepaper-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/LEPAPER">Practice</a><br>
<a href="http://www.codechef.com/COOK28/problems/LEPAPER">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM-HARD</p>
<h1>PREREQUISITES</h1>
<p>Dynamic Programming, Matrix Exponentiation</p>
<h1>PROBLEM</h1>
<p>You are given an array, say S, of size 1 x Z. Each value is between 1 and C.</p>
<p>You can perform K operations of the following type.</p>
<ul>
<li>Pick a range L, R.</li>
<li>Paint all the cells between L and R, inclusive, with some color between 1 and C.</li>
<li>You can only re-color a cell once.</li>
</ul>
<p>Find the number of different re-colorings of the paper, after performing at most K operations described above. Note that you have to find the number of re-colorings possible, not the number of ways of achieving the re-colorings.</p>
<h1>QUICK EXPLANATION</h1>
<p>Anton Lunyov came up with changes to this problem to make it harder and provided the judge solution for it. He also produced notes regarding parts of his solution. This Editorial is largely based on those notes and an analysis of his solution (which is well commented as well).</p>
<p>Let us look at a Dynamic Programming approach that would be too slow. We will be converting this in the Explanation section below, into a faster Matrix Exponentiation.</p>
<p>Visualize any coloring of the cells as broken up into blocks of similar colored cells. No re-coloring will ever take place to recolor a cell from its original color onto the same color. In other words, no wasteful operation will ever be performed. This helps us in defining the following Dynamic Programming state (on which we will see how we derive it from sub-states).</p>
<p><b>DP'[n,k]</b> = Number of ways of re-coloring the first n cells, in not more than k operations, such that the last block of same colored cells was not re-colored from their original colors.</p>
<p><b>DP[n,k,c]</b> = Number of ways of re-coloring the first n cells, in not more than k operations, such that the last block of same colored cells, are re-colored c. c may or may not be the original color that they had. If c is the original color that they had, then the recoloring certainly extends further to the left.</p>
<p>Note: Do not confuse between DP'[n,k] and DP[n,k,S[n]]. DP'[n,k] considers recolorings in which the last block of color S[n] is smaller than or equal to the length of the block in the original coloring (we use the term original length in the discussion below). Where as DP[n,k,S[n]] considers recolorings in which the last block of color S[n] is strictly larger than the original length.</p>
<p>Now,</p>
<pre>DP'[n,k] = DP'[n-1,k] + Summation( DP[n-1,k,x], x = 1 to C, except x = S[n] )
</pre>
<ul>
<li>DP'[n-1,k] considers all colorings in which the (n-1)<sup>th</sup> cell is the same color as the original, and the block containing it has not been recolored.</li>
<li>Summation( DP[n-1,k,x], x = 1 to C, except x = S[n] ) considers all the possible colorings in which the block ending at (n-1)<sup>th</sup> cell has any color beside S[n].</li>
<li>The case of S[n] must be ignored because<ul>
<li>It will be counted in DP'[n-1,k] if S[n-1] = S[n]. This will ensure that the length of that block doesn't exceed the original length.</li>
<li>All cases in which the last block of color S[n] is larger than the original length, will be counted in DP[n,k,S[n]] separately, and must not be counted here.</li>
</ul>
</li>
</ul>
<pre>DP[n,k,c] = DP[n-1,k,c], if c = S[n]
= DP[n-1,k,c] + DP'[n-1,k-1]
+ Summation( DP[n-1,k-1,x], x = 1 to C, except x = c ), if c != S[n]
</pre>
<ul>
<li>DP[n-1,k,c] considers the case where (n-1)<sup>th</sup> cell is also being recolored to c.</li>
<li>The operation will simply extend to the n<sup>th</sup> cell.</li>
<li>Note that when c = S[n], this recursion ensures that cases in which the length of the last block is longer than the original length are the only ones being considered.</li>
<li>Now, we consider cases where we are consuming one operation to recolor the last cell to c.</li>
<li>DP'[n-1,k-1] considers all the cases where the (n-1)<sup>th</sup> cell is not recolored (and the block ending at n-1 is not larger than the original length).</li>
<li>Summation( DP[n-1,k-1,x], x = 1 to C, except x = c ) considers all the cases in which the block ending at (n-1) is re-colored.</li>
<li>We ignore when the color is c, since this is being taken care of within DP[n-1,k,c].</li>
<li>The case when x = S[n-1] counts colorings where the block ending at (n-1)<sup>th</sup> is longer than the original length.</li>
</ul>
<p>Thus, the answer for a given case would be</p>
<pre>DP'[N,K] + Summation( DP[N,K,x], for all x = 1 to C )
</pre>
<p>This looks like it would lead to an O(N*C<sup>2</sup>*K) algorithm.</p>
<p>We can speed up the algorithm by a factor of C, by using</p>
<pre>D"[n,k] = Summation( DP[n,k,x], for all x = 1 to C )
</pre>
<p>This modifies the equations as</p>
<pre>DP'[n,k] = DP'[n-1,k] + D"[n-1,k] - DP[n-1,k,S[n]]
DP[n,k,c] = DP[n-1,k,c], if c = S[n]
= DP[n-1,k,c] + DP'[n-1,k-1] + D"[n-1,k-1] - DP[n-1,k-1,c]
</pre>
<p>Note the method 'slow' in the Tester's solution for a clear implementation of this approach. This approach would solve a large variety of cases. It is recommended that you implement this approach and visualize which colorings were counted under what path of the recursion to make it clear.</p>
<h1>EXPLANATION</h1>
<p>In the problem we note that</p>
<ul>
<li>Z can be very large</li>
<li>C can be very large</li>
<li>K is very small (up to 7)</li>
<li>There are very few unique colors in the paper originally.</li>
<li>This becomes very useful in considering all the other colors together.</li>
</ul>
<p>The Tester's solution implements a transition matrix that is derived from the DP formulation above and applies exponentiation over it for each of the block given in the input. This gives us a O(N*(N*K)<sup>3</sup> log max(M<sub>i</sub>)) algorithm to solve the problem.</p>
<p>The solution is heavily commented for building the Transition Matrix. It is recommended to go over it for reference on how you could go about doing the same.</p>
<p>There is one tricky detail in conversion of the DP to the Transition Matrix. We cannot consider all values of C. We only consider those values that are present in the original paper (at most 7). And, we consider one special value, let us say c = 0, which is meant to be helpful in considering any other color.</p>
<p>The matrix state would look like</p>
<pre>For some n (initially 0)
[
D'[n,0],
D'[n,1],
...
D'[n,K],
DP[n,0,0],
DP[n,1,0],
...
DP[n,K,0],
DP[n,0,C[1]],
DP[n,1,C[1]],
...
DP[n,K,C[1]],
...
...
DP[n,0,C[j]],
DP[n,1,C[j]],
...
DP[n,K,C[j]]
]
</pre>
<p>Where there are j different colors given.</p>
<h1>SETTERS SOLUTION</h1>
<p>Not Available.</p>
<h1>TESTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/COOK28/Tester/LEPAPER.cpp">here</a>.</p>gamabuntaMon, 19 Nov 2012 06:56:49 +0530https://discuss.codechef.com/questions/3949/lepaper-editorialdynamic-programminghardcook28editorialmatrix-expoHow do I solve SEQUA by using Matrix-exponential or sum of G.P ?https://discuss.codechef.com/questions/107097/how-do-i-solve-sequa-by-using-matrix-exponential-or-sum-of-gp<p>Please tell me how to approach <a href="https://www.codechef.com/ISCC2017/problems/SEQUA">SEQUA</a> by using Matrix-exponential or sum of Geometric progression ? </p>bansal1232Sun, 30 Jul 2017 02:41:40 +0530https://discuss.codechef.com/questions/107097/how-do-i-solve-sequa-by-using-matrix-exponential-or-sum-of-gpnumber-theorymatrix-expoDEVLOCK - Editorialhttps://discuss.codechef.com/questions/64620/devlock-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/DEVLOCK">Practice</a> <br>
<a href="http://www.codechef.com/FEB15/problems/DEVLOCK">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/dpraveen">Praveen Dhinwa</a> with help of <a href="http://www.codechef.com/users/alex_2oo8/">Alexey Zayakin</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a> and <a href="http://www.codechef.com/users/pushkarmishra">Pushkar Mishra</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/elfus">Florin Chirica</a> </p>
<h1>PREREQUISITES</h1>
<p>dp, fft, karstuba, binomial theorem, multinomial theorem, combinatorics, matrix exponentiation</p>
<h1>PROBLEM</h1>
<p>Find number of numbers of $N$ digits divisible by $P$ having their sum of digits $\leq M$. As number could grow very large, print answer modulo $998244353$. </p>
<h1>CREDITS</h1>
<p>I want to thank Praveen Dhinwa for helping me in writing some parts of the editorial. I have also incorporated ideas from Alexey and Shang too.</p>
<h1>QUICK EXPLANATION</h1>
<p>We will visualize the process of creating n digit number from left to right (i.e. from LSB (Lowest significant bit) to MSB (Most significant bit)). This visualization will help us in constructing a typical dynamic programming solution. </p>
<p>We can first write a simple dp having states (current place, sum of digits, remainder). It is too slow and only pass subtask 1. </p>
<p>But we can optimize it by using the fact that $P$ is too small. We can observe that putting $x$ at the $i^{th}$ place (from LSB to MSB) contributes $(x * 10^i) \, \% \, P$ into
the remainder and it adds $x$ to the sum of digits. Let us say $10^i \, \% \, P$ to be contributing remainder by $i^{th}$ digit to the number formed.</p>
<p>We will group the places by their contributing remainders. </p>
<p>So we will do a dp in which we will iterate over their contributes remainders (which goes from $0$ to $P - 1$ rather than $N$). </p>
<p>Let us make an array $cnt[i]$ which denotes number of places having contributing remainder equal to $i$.
Mathematically it is number of $x (0 \leq x < N)$ such that $10^x \% P = i$. For finding this $cnt$ array, you can simply use digit dp.
You can also use the fact of periodicity of $10^x \% P$. </p>
<p>At this point, you can also make an interesting and useful observation that distinct values of $cnt[i]$ won't be too much.
There indeed will be at most $4$ distinct values of $cnt[i]$ and these are $(0, 1, x - 1, x)$ for some $x$. It can be easily proved if we consider
how to calculate $cnt[i]$ using the fact that $(10^i \mod P)$ is periodic.</p>
<p>Let us define function $f: f[i][d]$ as number of ways of having sum of digits = $d$ for all the positions having contributing
remainder equal to i.</p>
<p>If we know how to compute $f$ faster, then we can use an $\mathbb{O}(M^2 P^2)$ dp to solve the third subtask. State of that
dp will be (at which contributing remainder we currently are, cur_sum_of_digits, cur_rem):</p>
<p>For computing $f$ faster, we can use matrix exponentiation, binomial theorem, multinomial theorem and combinatorics ideas, Few very basic details are given in this section.
Please see next section fore more details.</p>
<p>Let's fix contributing remainder as $r$, Let $f[i][d]$ denote the number of ways having first $i$ places of number we want to construct such that it is having sum of digits equal to $d$.
Note that we are considering in all the positions having contributing remainder equal to $r$.</p>
<ol>
<li>
<p><strong>Matrix exponentiation:</strong> <br>
$f[i][d]$: $\sum_{cur = 0}^{9} (f[i - 1][d - cur])$.
For a fixed contributing remainder $r$, As $i$ goes from $0$ to $cnt[r]$. We can compute it using matrix exponentiation.</p>
</li>
<li>
<p><strong>Binomial theorem:</strong> <br>
$f[i][d]$ is equal to number of solutions of $a_1 + a_2 + a_cnt[r] = d$ where $0 \leq a_i \leq 9$.
It is equal to coefficient of $x^d$ in the expression $(1 + x + x^2 + . . + x^9)^cnt[r]$.
Rewriting it smartly as discussed by us will do our task :)</p>
</li>
<li>
<p><strong>Multinomial expressions:</strong> <br>
Please just mention that you can write the above expression in a polynomial in two variables too, which can be helpful in solving
some problems. Note that, here multinomial expression can be reduced in binomial expression using the property that for a fixed remainder $r$, if you are making sum of digits equal to $x$, then
it will contribute $r * x \% P$ in the overall remainder.
Note that if $M \leq 50$ (subtask 2), you can find the above expression very fast using the idea of multinomial theorem.
You can write the above expression as using partition function over cnt[r].</p>
</li>
<li>
<p><strong>Combinatorics:</strong> <br>
Using some conbinatorial identity and inclusion exclusion, you can get an expression for $f$ too.</p>
</li>
</ol>
<p>Let us write a bivariate polynomial as follows.
$$
\large \prod_{i = 0}^{P - 1} \sum_{j = 1}^{m} coef[i][j] x^j y^{(i j) \% P)}$$</p>
<p>We have to find coefficient of $x^m y^0$ in it. Note that we can convert this bivariate polynomial into univariate by using a smart trick described in next section.</p>
<p>As we noticed the DP transition is a multiplication by some matrix. We can notice that this matrix has exactly $P$ independent components (each of size $M + 1$), thus we can consider these components independently. Inside each component multiplication by matrix is equal to multiplication by some polynomial which can be done by FFT or Karatsuba's multiplication algorithm.</p>
<h1>EXPLANATION</h1>
<p><strong>Simplest DP idea for solving subtask 1</strong></p>
<p>Let's start by solving the problem using a simple DP. We need to count strings of length $N$, with sum of digit $X$, which are divisible by $P$. Since it's a counting problem, we can try solving it by DP. The DP depends on the number of digits added so far, their remainder modulo $P$ and their sum of digits. </p>
<p>Let $dp[n][rem][sum]$ = how many strings of length $n$ have remainder rem modulo $P$ and their sum of digit is $sum$. The answer is obviously $dp[N][0][X]$. The standard initialization in counting problems is to consider a "fictitious" string - of length $0$ (like we added nothing). In this case, adding nothing translates to $dp[0][0][0] = 1$.</p>
<p>Let's see the recurrence. How can we reduce the problem from length $N$ to length $N - 1$? By fixing the first digit (for example). Suppose the first digit is $c$. It adds $10^n*c$ to the remainder and also it adds $c$ to the sum of digits. So let's iterate $c$ from $0$ to $9$. Now first digit is fixed. How to count the rest? We need to add to $dp[n][rem][sum]$ the value $dp[n - 1][rem'][sum - c]$, where $rem' + 10^n * c = rem$. </p>
<p>This approach times out for big values of $n$, but it's fast enough to pass the first subtask.</p>
<p><strong>Let's change the DP</strong></p>
<p>We somehow have to get rid of that $n$ factor. Let's take a closer look to what DP actually does - the value of $n$ is important because it determines value of $10^n * c$, for the first digit added. But now it comes the interesting part - that is $10^n$ $modulo P$. This means, there are only $P$ possible distinct answers for all $10^n$ values. This means, we can group the values $n$ by the value $10^n modulo P$. </p>
<p>What do we get by doing this? The idea is to add digits for a group <em>at the same time</em>. Let's Denote $cnt[x]$ = number of values $y (0 \leq y < N)$ such as $10^y mod P = x$. Let's assume for now this array calculated. </p>
<p>Suppose we know that $cnt[0] = 4$ and $cnt [1] = 3$ . There will be $4$ positions (let's note them $p_1, p_2, p_3, p_4$) such as $10^{p_1} = 10^{p_2} = 10^{p_3} = 10^{p_4} = 0 (modulo P)$. If we assign them digits d1, d2, d3, d4, the remainder modifies by $10^{p_1} * d1 + 10^{p_2} * d2 + 10^{p_3} * d3 + 10^{p_4} * d4 = 10^{p_1} * (d1 + d2 + d3 + d4) = 0 * (d1 + d2 + d3 + d4) = 0.$ Let's consider the other example: $cnt [1] = 3.$ There will be 3 positions (p1, p2, p3) such as $10^{p_1} = 10^{p_2} = 10^{p_3} = 1 (modulo P)$. If we assign them digits d1, d2, d3, the remainder modifies by $10^{p_1} * (d1 + d2 + d3) = 1 * (d1 + d2 + d3)$.</p>
<p>The idea is to iterate over $i$ from $0$ to $P - 1$. Let's consider $cnt[i]$ positions for the given $i$. We can fix what digits we add. They will have a sum of digits (let's note it $sd$). Then, the remainder modifies by $i * sd$ and sum of digits modifies by $sd$.</p>
<p>We have a new DP. Let $dp[g][rem][sum]$ = in how many ways can we obtain remainder rem modulo $P$ and sum of digits $sum$ if we considered <em>only</em> first $g$ groups of positions $(cnt[0], cnt[1], ..., cnt[g - 1])$. </p>
<p>For the current group we can iterate the sum of digits we assign to it. This uniquely modifies the remainder and the sum of digits. So, for a calculated $dp[g][rem][sum]$, let's iterate $sd$, representing sum of digits added for positions corresponding to group $g + 1$.</p>
<p>We get the recurrence $dp[g + 1][(rem + g * sd) \, \% \, P][sum + sd]$ += $dp[g][rem][sum] * ways[g][sd]$. You probably wonder what ways can be. We assigned a sum of digits. It needs to be divided between $cnt[g + 1]$ positions. This means, we need to assign to cnt[g + 1] positions values between 0 and 9 such as, after adding all those values from the positions, we get the sum sd. This is ways[g][sd] = in how many ways can we distribute sum of digits sd to $cnt[g]$ positions, such as in each positions we're allowed to add numbers between 0 and 9.</p>
<p>If we can calculate tables cnt and ways efficiently, we're done. We'll calculate firstly cnt, then ways.</p>
<p><strong>Calculating values of cnt</strong></p>
<ol>
<li>
<p><strong>Using periodicity of $10^y \% P$</strong> <br>
First one, let's suppose you calculate $10^0, 10^1, ..., 10^P$. There are P + 1 values but only P possible remainders (from 0 to P - 1). By pigeon principle, it means that at least two values are equal. Suppose $10^x = 10^y (mod P)$, with x < y. I'll claim that all possible values are $10^0, 10^1, ..., 10^x, ..., 10^{y-1}, 10^x, ...., 10^{y-1}, 10^x, ..., 10^{y-1}.$ In other words, after calculating at most P values, the sequence becomes cyclic. This is because $10^{x+1} = 10^{y+1}$ (we simply multiplied by 10), $10^{x+2} = 10^{y+2}$ (we multiplied the last equality by 10) and so on. So it's enough to find the period
and update the cnt array.</p>
</li>
<li>
<p><strong>Digit dp solution</strong> <br>
The second method does not require any observation. We can simply do digit DP. This means we add digits of x one by one and remember, for each prefix, the remainder of $10^x$ modulo P. Suppose we have a prefix Pr with remainder r (remainder of 10^Pr modulo P). Then, we can extend Pr by a digit c. The new power of 10 will be
$10^{Pr*10+c} = 10^{Pr * 10} * 10^c = r^{10} * 10^c$. So we'll have to add all prefixes Pr of length n which give remainder r to all prefixes of length n+1 which give remainder $r^{10} * 10^c$. Now let's think what digits c we can add to a prefix. There are two cases:</p>
<ul>
<li>
<p>the prefix is identical to one prefix of n. In this case, we must be careful not to add a digit such as the prefix will be greater than n. We can add only digits up to current digit of n. </p>
</li>
<li>
<p>the prefix is not identical to one prefix of n. In this case, we can add all digits from 0 to 9.</p>
</li>
</ul>
<p>This leads us to digit_dp[same][rem][n] = how many prefixes of length n have remainder rem of $10^{prefix}$ modulo P with (same = 0 means the current prefix is different to prefix of n and same = 1 means the current prefix is the same with the prefix of n).</p>
</li>
</ol>
<p>Using one of those approaches, we can compute array cnt.</p>
<p><strong>Calculate the array ways</strong></p>
<p>As a quick recap: ways[g][sd] = in how many ways can we split sum of digits sd to cnt[g] positions. Denote by now n = cnt[g]. We have to count how many equations satisfy: </p>
<p>$x[1] + x<a href="http://en.wikipedia.org/wiki/Composition_%28combinatorics%29">2</a> + .... + x[n] = sd$ such that $0 \le x[i] \le 9$</p>
<p>This is a classical problem. There are lot of ways of solving such problem. </p>
<ol>
<li>
<p><strong>Generating function and binomial expression solution</strong> </p>
<p>I'll describe some approaches to do it. One of them is to associate a polynomial for this expression</p>
<p>$(1 + x^1 + .... + x^9) ^ n$ and we're interested in the coefficient of $x^{sd}$. Why does it work? Just try to simulate the calculations on paper... you'll probably see it.</p>
<p>Let's rewrite S = $1 + x^1 + ... + x^9$ using geometric progressions. I'll write here how to deduce it, without knowing the formula for a geometric progression.</p>
<p>$S = 1 + x^1 + ... + x^9$</p>
<p>$x*S = x^1 + x^2 + .... + x^{10}$</p>
<p>$S*(x - 1) = x^{10} - 1$</p>
<p>$S = \frac{(x^{10} - 1)}{(x - 1)}$</p>
<p>So the problem reduces to find the coefficient of $x^{sd}$ in $\frac{(x^{10} - 1) ^ n}{(x - 1) ^ n}$. The trick is to write the expression as $(x^{10} - 1) ^ n * (x - 1) ^ {-n}$. Let's note</p>
<p>First term = $(x^{10} - 1) ^ n$</p>
<p>Second term = $(x - 1) ^ {-n}$</p>
<p>We'll split coefficient of $x^{sd}$ in two parts: let's say that we need to get $x^i$ from the first term and $x^{sd - i}$ from the second term (we iterate this i). We have two problems left: find the coefficient of $x^i$ in the first term and find the coefficient of $x^{sd - i}$ in the second term.</p>
<p>We'll take i values only multiples of 10 (because otherwise there is no chance to find $x^i$ in the first term). Now we can simply apply binomial theorem to get it.</p>
<p>For second term it is more tricky, as we have negative powers. However, this <a href="http://math.stackexchange.com/questions/85708/negative-exponents-in-binomial-theorem">link</a> explains it pretty well.</p>
<p>If considering also the remainder, this can be solved by multinomial expressions too. As each operations increases the remainder by g, we can consider a polynomial in two variables: $x^i * y^{g*i}$. The power of x corresponds now to the number of used operations for a given position and the power of y corresponds now to the "gained" remainder after doing the operations.</p>
<p>So we can also write the expression as $(x^0 * y^0 + x^1 * y^g + .... + x^9 * y^{9 * g}) ^ n$. We're now interested in the coefficient $x^n * y^{sd*g}$. We can now use multinomial theorem to solve it.</p>
<p>Finally, this can be solved by combinatorics and inclusion and exclusion principle. Let's define F(n, pos) = how many solutions are for equation $x_1 + x_2 + ... + x_n = sd$ such as <em>at least</em> pos positions have x[i] > 9. </p>
<p>Let's note that something like 1+10+10 will be added twice in F(3, 1): once for position 2 and once for position 3.</p>
<p>How can we use this idea? Initially, the answer is F(n, 0). However, some elements can have values > 9. Let's erase those who have one position with elements > 9. This is F(n, 1). What now? It was possible we erased twice some arrays: those having two positions > 9. How to fix this? We add F(n, 2). Next, we erase F(n, 3) and so on. This is called inclusion and exclusion principle.</p>
<p>How to get F(n, k)? Let's fix firstly the positions which <em>must</em> have elements > 9. We can choose them in $\binom {n}{k}$ ways. We add 10 to those positions, to <em>force</em> them to have value > 9. Now, on the other positions, we may or we may not have values > 9, there is no restriction left. So we're left with solving</p>
<p>$x_1 + x_2 + ... + x_n = sd - k * 10$ (since we forced the chosen positions to have value at least 10).
such as x[i] >= 0</p>
<p>This problem is a classical one, you can read more about it <a href="http://en.wikipedia.org/wiki/Composition_%28combinatorics%29">here</a>. So F(n, k) is $\binom {n}{k} * \binom {sd + n - 1 - 10 * k}{n - 1}$. Binomial coefficient can be calculated using Pascal's triangle.</p>
</li>
<li>
<p><strong>Matrix exponentiation</strong> <br>
You can write the above expression as a dp in which the matrix with which you are multiplying to get next state is constant. So you can use matrix exponentation for that.</p>
</li>
<li>
<p><strong>Combinatorics based solution</strong> </p>
<p>Let $t = cnt[i]$.
$a_1 + a_2 + + . . + a_t = d.$
Assume that $a_i \geq 0$ is only constraint.
Then number of solutions will be $\binom{d + t - 1}{t - 1}$. Explanation for this is usually given by beggar method.</p>
<p><em>Idea of inclusion exclusion:</em> <br>
Now as in the above case, our a_i is unbounded, we need to bound them by 9.
Now we know that some of the variables will go larger than t, we will count them smartly using inclusion exclusion.</p>
<p>Using these ideas, you can get a combinatorial solution for computing f.</p>
<p>More details about this method will be added later if requested by participants. </p>
</li>
<li>
<p><strong>Multinomial theorem</strong>
One of the possible ways to compute $F$, to use multinomial theorem. You can simply write the above expression as a multinomial expression. I will add details about this method later. You
can see Praveen's Solution for it.</p>
</li>
</ol>
<p><strong>Solving the hardest subtask</strong> </p>
<ol>
<li>
<p><strong>Using bivariate polynomial multiplication</strong> <br>
Let us write a bivariate polynomial as follows.
$$
\large \prod_{i = 0}^{P - 1} \sum_{j = 1}^{m} coef[i][j] x^j y^{(i j) \% P)}$$</p>
<p>We have to find coefficient of $x^m y^0$ in it. Note that we can convert this bivariate polynomial into univariate by using a trick that we can represent powers of both
$x$ and $y$ cumulatively in base $(2 * m + 1)$. So replacing $y$ by $x^(2 * m + 1)$ in the bivariate polynomial will convert it to univariate polynomial.
Note that $x^p_1 y^p_2$ will be represented as a number $p_2 p_1$ in base $2 * m + 1$, whose actual value will be $p2 * (2 * m + 1) + p1$.
So maximum degree of univariate polynomial won't be larger than $\mathbb{O}(m * p)$. Multiplying two polynomials in a prime field can be done using Number Theoritic Transform. You
can use some tricks to multiply two polynomials for any modulo. For this problem, you only needed to use simple Number Theoritic Transform.</p>
</li>
<li>
<p><strong>Using M * P univariate polynomial multiplications</strong> <br>
Alexey came up with the idea to reduce the complexity to $\mathbb{O}(P * M^2 + P^2 * Mlog_2(3))$. As you noticed before the DP transition is a multiplication by some matrix. We can notice that this matrix has exactly $P$ independent components (each of size $M + 1$), thus we can consider these components independently. Inside each component multiplication by matrix is equal to multiplication by some polynomial and this can be done in $\mathbb{O}(M log M)$ time using FFT or in time $\mathbb{O}(M log_2(3))$ using Karatsuba multiplication algorithm.</p>
</li>
</ol>
<p>Actually theoritically the first method should be faster, but practically, the second method worked slightly faster than first method. You can see [Praveen's solution][] for solution based on the first
method. Please see [Alexey's Solution][] for second method.</p>
<p><strong>Reasons for not hiding modulo</strong> <br>
Actually initially we had intended to use $10^9 + 7$ as modulo, but already the solution was taking around 12 secs, For having $10^9 + 7$ as modulo, we needed to 3 times FFT multiplications. Then the bruteforce
solution becomes fast enough to pass this kind of subtask. So we just decided to use typical NTT modulo. </p>
<p>Please share any other idea you have regarding the problem !!</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/FEB15/Setter/DEVLOCK.cpp">Setter's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/FEB15/Tester1/DEVLOCK.cpp">Tester's solution</a></p>adminMon, 16 Feb 2015 15:23:57 +0530https://discuss.codechef.com/questions/64620/devlock-editorialcombinatoricsfftmatrix-expodynamic-programmingmedium-hardfeb15mathYouTube Tutorial : Matrix Exponentiation + Dynamic Programminghttps://discuss.codechef.com/questions/109222/youtube-tutorial-matrix-exponentiation-dynamic-programming<p>Hi everybody,</p>
<p>In the continuation of my Dynamic Programming Tutorial Playlist, <br>
I've finally launched the <a href="https://www.youtube.com/watch?v=TTtOpv6Hrcg">2nd video</a> which is based on Matrix Exponentiation and Dynamic Programming. <br>
If you haven't watched the <a href="https://youtu.be/tb_14w_-mNw">1st video</a>, do watch it before as this video is a continuation of previous one.</p>
<p>Feedbacks are most welcome :) <br>
If you like my work, please like the videos and subscribe to my channel. <br>
Also share it with friends in your college too. </p>
<p>I am happy to see that the family has grown out to 450 subscribers in just 4/5 days.</p>rachitiitrWed, 23 Aug 2017 13:03:39 +0530https://discuss.codechef.com/questions/109222/youtube-tutorial-matrix-exponentiation-dynamic-programmingdynamic-programmingvideo-lecturetutorialmatrix-expoNPLFSEQ - Editorialhttps://discuss.codechef.com/questions/115894/nplfseq-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/NPLFSEQ/">Practice</a>
<br>
<a href="https://www.codechef.com/NPLF2017/problems/NPLFSEQ/">Contest</a></p>
<p><em>Author:</em> <a href="https://www.codechef.com/users/vinod10">vinod10</a> <br>
<em>Editorialist:</em> <a href="https://www.codechef.com/users/vinod10">vinod10</a> <br></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p><a href="http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html">Matrix Exponentiation</a> , <a href="http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/">Modular multiplicative inverse</a></p>
<h1>PROBLEM:</h1>
<p>Given a sequence f(n) = A * f(n-1) + B * f(n-2), ( with base case f(1)=f(2)=1 ), find sum of f(n) where l<=n<=r. Find this sum for Q queries.</p>
<h1>QUICK EXPLANATION:</h1>
<p>S(l,r) = f(l) + f(l+1) + ..... +f(r) = { f(r+2) - f(l+1) + (A-1) * ( f(l) - f(r+1) ) } / {A+B-1}. Now using matrix exponentiation, f(X) can be found in logX time. Hence each query can be solved in LogN time.</p>
<h1>EXPLANATION:</h1>
<p>Given, <br></p>
<p>f(l) = A * f(l-1) + B * f(l-2).<br></p>
<p>f(l+1) = A * f(l) + B * f(l-1).<br>
.<br>
.<br>
.<br></p>
<p>f(r-1) = A * f(r-2) + B * f(l-3).<br></p>
<p>f(r) = A * f(r-1) + B * f(r-2).<br></p>
<p>Summing these all will give: <br></p>
<p>S(l,r) = A * ( S(l,r) - f(r) + f(l-1) ) + B * ( S(l,r) - f(r) - f(r-1) + f(l-1) + f(l-2) ).</p>
<p>Simplifying it gives:
S(l,r) = { f(r+2) - f(l+1) + (A-1) * ( f(l) - f(r+1) ) } / {A+B-1}<br></p>
<p>Now calculation of f(n) requires knowledge of matrix exponentiation, and if you are not familiar with it, you can follow <a href="http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html">this</a> blog.</p>
<p>We know : </p>
<p>$$
\left(\begin{array}{cc}
f(n) & f(n-1)\\
f(n-1) & f(n-2)
\end{array}\right)
\left(\begin{array}{cc}
A & 1\\
B & 0
\end{array}\right)
=
\left(\begin{array}{cc}
f(n+1) & f(n)\\
f(n) & f(n-1)
\end{array}\right)
$$ </p>
<p>therefore, </p>
<p>$$
\left(\begin{array}{cc}
A+B & 1\\
1 & 1
\end{array}\right)
\left(\begin{array}{cc}
A & 1\\
B & 0
\end{array}\right)^{n-3}
=
\left(\begin{array}{cc}
f(n) & f(n-1)\\
f(n-1) & f(n-2)
\end{array}\right)
$$ </p>
<p>Using matrix multiplication M^{N-3} can be calculated in logN time. Hence we calculate each term in the answer and to divide the final answer by {A+B-1}, we use modular multiplicative inverse. Notice 10<sup>9</sup>+7 is a prime, hence <a href="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem">Fermat's little theorem</a> can be used to get modular multiplicative inverse of {A+B-1}, which is {(A+B-1)<sup>MOD-2</sup>} % MOD, where MOD = 10<sup>9</sup>+7.</p>
<h1>AUTHOR'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://www.codechef.com/viewsolution/16025240">here</a>. <br></p>vinod10Wed, 01 Nov 2017 13:33:07 +0530https://discuss.codechef.com/questions/115894/nplfseq-editorialnplfseqnplf2017matrix-expoANURAJ - EDITORIALhttps://discuss.codechef.com/questions/120924/anuraj-editorial<h1>Anupam and Raja</h1>
<p><strong>Problem Setter:</strong> <a href="https://www.codechef.com/users/soham1234">Soham Mukherjee</a></p>
<p><strong>Problem Tester:</strong> <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a></p>
<h2>Problem:</h2>
<p>Given a graph with N vertices and E edges, with each vertex holding a value, initially zero. We are required to print these values at vertices <strong>MOD 1e9+9</strong>, where each query is described as:</p>
<ol>
<li>Given two integers u and k, add $dist(u,vertex) + F(k)$ to all vertices, $dist(u,v)$ is the smallest distance between u and v.</li>
<li>Function $F(K)$ is defined as: Number of was of selecting subset of points such that no two selected points are consecutive. First and last points are also considered consecutive.</li>
</ol>
<h2>Solution:</h2>
<p>This problem can be solved using two insights:</p>
<ul>
<li>That $F(K)$ is entirely independent of graph edges and values, and thus, can be calculated separately.</li>
<li>Now, Since there is no modification query on graph, $dist(u, v)$ remains same, and thus, can be calculated in advance. Also, N is set to max 300, which allow use to make a $dist[N][N]$ array, storing pairwise distances.</li>
</ul>
<p>Now, the problem is solved in two parts:</p>
<h3>Getting the value of $F(K)$ in O(logK) time (Since K <= 1e9 for worst case).</h3>
<p>This part can be solved using matrix Exponentation.</p>
<p>If you are good at combinatorics, and had recognized the pattern, feel free to skip following para.</p>
<p>A good approach to solve such pattern problems is to make a guaranteed correct solution (usually slower for constraints, like bitmask, sub-linear or N^2 solution, depending upon problem). Then trying to recognize the recurrence, the relation between consecutive (or alternate) terms. This solves most of the series problems. </p>
<p>For F(k), We can build a bitmask solution to determine F(K) for smaller values.</p>
<p>By our slower solution, we will see the sequence, starting from F(1), as</p>
<p>2 3 4 7 11 18 29 47</p>
<p>If we ignore the first term of this sequence, we have a fibonacci sequence with first term 3 and 4.</p>
<p>F(1) was an edge case, because We can select out of 1 elements, two subsets, {} and {1}, hence F(1) = 2. But it does not satisfy the above fibonacci sequence. So, we handle K == 1 separately and for rest values, calculate F(K) using matrix exponentation (Same way as that for finonacci sequence). Refer <a href="https://www.geeksforgeeks.org/matrix-exponentiation/">this</a> for details on matrix exponentation and <a href="https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/">this</a> discuss in details various ways of calculating fibonacci numbers. I am leaving implementation upon you. </p>
<h3>Creating Dist array and handling queries.</h3>
<p>For pairwise distance grid, FLoyd warshall's All Pairs shortest path problem in runtime O(N^3). Test cases were set to fail repeated dijkstra and Bellman ford algorithms for each nodes. Details about Floyd warshall can be read <a href="https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/">here</a>.</p>
<p>So we have the dist array, we run each query as, calculate value of F(K) once, run loop on each vertex, adding value + dist[u][i] to ith node.</p>
<p>Print answer mod (1e9+9). Notice different mod used here. Can result in WA, if problems statement not read carefully.</p>
<p><a href="https://www.codechef.com/viewsolution/16754081">Editorialist's solution.</a></p>taran_1407Thu, 04 Jan 2018 22:42:45 +0530https://discuss.codechef.com/questions/120924/anuraj-editorialfloyd-warshallanurajicop1806easymatrix-expo