In the problem Gandhian Series…my code’s complexity is O(T*k) I guess which is feasible to solve the problem still it is showing TLE

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

Please have a look at this

I know that problems of this type where we have to get the summation of 1^k + …+ 2^k

we have to do them in O(k)

still TLE…Why

help!!!

```
m = k + 1
for i in range(2, m):
temp = 0
for j in range(0, i):
temp -= binom(i + 1, j) * S[j]
temp %= p
# print(temp)
temp -= (1 - (n + 1) ** (i + 1))
```

These bits are your problem. The inner loop has complexity O(k^2) and the raising n to a silly power in total is O(k log(k)) before considering the length of things we’re multiplying (up to 12000 digits which is probably slower than the O(k^2) operation for the choices of parameters we’re interested in).

how to solve this problem? means how to find sum of series (1^k + 2^k + … + n^k) in o(K)?

it is given here in the editorial

thanks for sharing link.

I have updated the test files. Previously it was only changed for contest page. I have now changed it for both. Thanks for reminding. Sorry for the inconvenience caused!

I have taken this code from hackerrank Solution of “Summing the K-N series”

where constraints were like 1<=n<=10^18 and 1<-k<=1000…

still it works there for T queries…

and what should I do to improve its complexity…

Thank you in advance