# Toughest mathematical problem COUNTIT

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:- https://www.codechef.com/viewsolution/24597687

1 Like

Not the toughest mathematical problem if you know FFT

1 Like

@anon55659401
Can u share something so that i can read it and understand how to solve this problem.

I was also unable to turn o(k) into O(m+n). Please somebody discuss their O(m+ n) approach.

1 Like

I’ve seen the interpolation solution but how do you do it with fft?

Here is a nice FFT solution I saw :- https://www.codechef.com/viewsolution/24509237
By @jtnydv25

3 Likes

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!!!

1 Like

Use lagrange interpolation (its O(n^2) but you can make it O(n) for this special case)
https://www.geeksforgeeks.org/lagranges-interpolation/

https://www.codechef.com/viewsolution/24832230

4 Likes

can you explain how to use fft ??
PS : I see lots of factorial and stuff so think its still tough maths in @jtnydv25 soln

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

1 Like

XD I am still a newbies like you

Guys, @l_returns haS turned 6, dream has come true <3

1 Like

I found O(k) formula using pattern XD

1 Like

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.

2 Likes

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. 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). This is mentioned in the codeforces blog but this editorial has a clearer and longer explanation.

Interpolation solutions seem way simpler though.

6 Likes

okay thanks

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. https://www.codechef.com/viewsolution/24756120

2 Likes