PROBLEM LINK:Author: Md Shahid Tester: Arkapravo Ghosh Editorialist: Md Shahid DIFFICULTY:Hard PREREQUISITES:Descrete Mathematics, Generating function and Modular Exponentiation PROBLEM:Given
QUICK EXPLANATION:The solution of the given recursive function is $f(n) = 2^n + 3n$. Use modular exponentiation to make your program run within time limit. EXPLANATION:This problem belongs to Discrete Mathematics. In the real life scenario, you also have to face such problem where there can be a recursive equation but you can not solve it recursively because recursion can cause your program to execute for a long time, in Competitive programming you will get time limit exceed(TLE) and as a competitive programmer you don't want it right. So here come two techniques to solve
this type of problem
Let $G(x) = \sum_{n=0}^{\infty} a_n x^{n}$ be generating function. Then $f(n) = 2f(n1) + f(n2) + 2^{n2}$ (1) when $n \geq 2$, $f(0) = 1$, $f(1) = 5$ Multiplying both sides of (1) by $x^n$ and summing from $n=2$ to ${\infty}$ $\sum_{n=2}^{\infty} a_n x^n  2 \sum_{n=2}^{\infty} a_{n1} x^n + \sum_{n=2}^{\infty} a_{n2} x^n$ $= \sum_{n=2}^{\infty} 2^{n2} x^n$ or $G(x)  a_0  a_1 x 2x(G(x)  a_0) + x^2 G(x) = \frac{x^2} {12x}$ Substituting a_0 =1, a_1 = 5 $(12x  x^2)G(x) = 1 + 3x + \frac {x^2} {12x} $ or $G(x) = \frac {1+x5 x^2}{(12x)(1x)^2}$ or $ G(x) = \frac {1}{12x}  \frac {3}{1x} + \frac {3}{(1x)^2}$ or $ G(x) = \sum_{n=0}^{\infty} (2x)^n  3 \sum_{n=0}^{\infty} x^n +3 \sum_{n=0}^{\infty} (n+1) x^n $ or $ G(x)= \sum_{n=0}^{\infty} (2^n  3 + 3(n+1)) x^n$ $a_n = 2^n  3 + 3(n+1) = 2^n + 3n $ $ \therefore a_n = 2^n + 3n$ AUTHOR'S AND EDITORIALIST'S SOLUTIONS:Author's and editorialist’s solution can be found here.
This question is marked "community wiki".
asked 15 Mar, 12:49
