# Toughest mathematical problem COUNTIT **URL:** \ **Category:** help\ **Tags:** junechallenge\ **Created:** [June 17, 2019, 11:15am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006 "2019-06-17T11:15:11Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![mr\_nastik](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mr_nastik/32/255412_2.png) [@mr\_nastik](https://discuss.codechef.com/u/mr_nastik)\ **Post date:** [June 17, 2019, 11:15am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/1 "2019-06-17T11:15:11Z")
i found the formula of COUNTIT thats solve the Problem in O(k) but i cant simplify it in O(n) or something like that… so 100 marks obtain… tell me the real solution how to simplify the formula or tell me the correct approach… my solution:- [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24597687) ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [June 17, 2019, 11:25am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/2 "2019-06-17T11:25:49Z")
Not the toughest mathematical problem if you know FFT 🙂 ---
**Author:** ![mr\_nastik](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mr_nastik/32/255412_2.png) [@mr\_nastik](https://discuss.codechef.com/u/mr_nastik)\ **Post date:** [June 17, 2019, 11:35am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/3 "2019-06-17T11:35:56Z")
@anon55659401 Can u share something so that i can read it and understand how to solve this problem.😅 ---
**Author:** ![sayanmedya](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sayanmedya/32/289916_2.png) [@sayanmedya](https://discuss.codechef.com/u/sayanmedya)\ **Post date:** [June 17, 2019, 11:38am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/4 "2019-06-17T11:38:10Z")
I was also unable to turn o(k) into O(m+n). Please somebody discuss their O(m+ n) approach. ---
**Author:** ![abdullah768](https://discuss.codechef.com/user_avatar/discuss.codechef.com/abdullah768/32/11498_2.png) [@abdullah768](https://discuss.codechef.com/u/abdullah768)\ **Post date:** [June 17, 2019, 12:00pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/5 "2019-06-17T12:00:48Z")
I’ve seen the interpolation solution but how do you do it with fft? ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [June 17, 2019, 12:11pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/6 "2019-06-17T12:11:43Z")
Here is a nice FFT solution I saw :- [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24509237) By @jtnydv25 🙂 ---
**Author:** ![naveen19991124](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naveen19991124/32/24644_2.png) [@naveen19991124](https://discuss.codechef.com/u/naveen19991124)\ **Post date:** [June 17, 2019, 12:20pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/7 "2019-06-17T12:20:55Z")
Isn’t COUNTIT a problem totally based on combinatorics.However,I tried to build up some matrices but couldn’t figure out any pattern or so.PLEASE HELP!!! ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 17, 2019, 12:32pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/8 "2019-06-17T12:32:14Z")
Use lagrange interpolation (its O(n^2) but you can make it O(n) for this special case) [Lagrange's Interpolation - GeeksforGeeks](https://www.geeksforgeeks.org/lagranges-interpolation/) [https://www.codechef.com/viewsolution/24832230](https://www.codechef.com/viewsolution/24832230) ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 17, 2019, 12:35pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/9 "2019-06-17T12:35:20Z")
can you explain how to use fft ?? PS : I see lots of factorial and stuff so think its still tough maths in @jtnydv25 soln 😛 ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [June 17, 2019, 12:36pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/10 "2019-06-17T12:36:05Z")
Congratulations for those 6-stars \<3 …As I already said you will be 6 this time B-) . Now, please write a post for us newbies on how to improve 🙂 ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 17, 2019, 12:36pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/11 "2019-06-17T12:36:51Z")
XD I am still a newbies like you 😉 ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [June 17, 2019, 12:37pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/12 "2019-06-17T12:37:24Z")
Guys, @l_returns haS turned 6, dream has come true \<3 ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 17, 2019, 12:40pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/13 "2019-06-17T12:40:30Z")
I found O(k) formula using pattern XD ---
**Author:** ![naveen19991124](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naveen19991124/32/24644_2.png) [@naveen19991124](https://discuss.codechef.com/u/naveen19991124)\ **Post date:** [June 17, 2019, 12:48pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/14 "2019-06-17T12:48:39Z")
Please can you tell me the category under which such topics fall so as to study them or should i learn by going through such questions only. ---
**Author:** ![mnaveenkumar20](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mnaveenkumar20/32/167217_2.png) [@mnaveenkumar20](https://discuss.codechef.com/u/mnaveenkumar20)\ **Post date:** [June 17, 2019, 12:52pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/15 "2019-06-17T12:52:12Z")
Since the formula is \sum \_{k=0} ^{K} (k^m-(k-1)^m)(k^n-(k-1)^n) If we write the inner part as a polynomial in k (Which we can do by just expanding it from the binomial theorem formula) we just need to find \sum \_{k=0} ^{K} k^i for all i from 0 to m+n. The fft is used for \sum \_{k=0} ^{K} k^i part as we can find that using bernoulli numbers (Faulhaber’s formula). The formula and method for the same is mentioned here. [Counting sums of powers - Codeforces](https://codeforces.com/blog/entry/60756). I used the method he mentioned in his reply to the first comment which convolves A and B (can use fft again for this, refer the post for what’s A and B). For the code to find Bernoulli numbers fast you can refer to MAY18A editorial for the problem SERSUM : [SERSUM - Editorial (reupload)](https://discuss.codechef.com/t/sersum-editorial-reupload/18702). This is mentioned in the codeforces blog but this editorial has a clearer and longer explanation. Interpolation solutions seem way simpler though. ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 17, 2019, 12:57pm UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/16 "2019-06-17T12:57:14Z")
okay thanks … ---
**Author:** ![megatron10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/megatron10/32/256270_2.png) [@megatron10](https://discuss.codechef.com/u/megatron10)\ **Post date:** [June 18, 2019, 4:16am UTC](https://discuss.codechef.com/t/toughest-mathematical-problem-countit/28006/18 "2019-06-18T04:16:05Z")
In my submission I have put up a comment about how to solve the problem, I did it with FFT. The links there will be good enough. Give it a read, here. [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24756120)