| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi all,
I made a short video on some nice observations about Power Sums of the form 1^n+2^n+3^n+.....+m^n and how to calculate formulae for them.
I hope this will be useful for some.
Let me know if you enjoyed the video and feedback / any questions in the comments below.
Hope you all have a good day! :)
Can you add practice problem for this topic? This topic is way beyond my rating but I have a keen love for math since years.
$$$1^k + 2^k + ... + n^k$$$ itself is here
stop cheating first
like this?
Nope, Like this BLATANT
Coming from a new acc like cheaters do so that they can't get exposed from their original id submissions. Get some guts to come from real id then we'll talk troll
u cheated though
Nope I didn't. There's just one skipped contest coz that solution happened to be similar to someone else. Can't help that. There'll be some minor similarities in some questions. It wasn't a copy though (and none of them are)
minor similarities (no).
notorious co-incidence (yes)
thanks!
O
At 12:30 in the video, you claimed that,
is a polynomial of degree n in m.
But shouldn't it be a polynomial of degree n+1 in m. Consider the following:
which is actually a polynomial of degree n+1.
Also, where is the final formula to get the required sum for $$$ \displaystyle m>=10^9 $$$ in $$$ \displaystyle O(n) $$$ ?
ig for the final sum we gotta use faulhaber polynomials. that would require counting for bernoulli numbers first
Stop cheating first
The final formula usually is just using the fact that it's a polynomial to do polynomial interpolation.
Got it. Thanks!
Please note that the one you described is essentially different as the highest degree of m in your case will be n+1 (as r goes from 0 to n+1) but in the formulae described at 12:30 (the power of k is n+1-r) so the max power of k will be when r=2 i.e n+1-2 = n-1 and thus the sum over k will be a polynomial of degree n (1 more than the power) in m and not n+1 and C(n+1,r) (r goes from 2 to n+1) does not depend on m, hence this will not change the degree of the polynomial
Using this method as it is described in the video I don't think so you can compute this in O(n), You can do something on the order of n^2 with this.
There are other ways for example Lagrange interpolation using which you can calculate it faster, I will upload a video later on this.
Ok understood.
I was actually thinking that even if you considered the second summation to be equal to 1. Even then the final answer would be $$$2^{n+1} +$$$ some constant. I was just focusing on the maximum power of $$$n$$$ occurring there and forgot the fact that the polynomial was a function of m.
nvm i was wrong
I realized that I used NTT to calculate Stiring numbers, then to get the answer. But Lagrange Interpolation doesn't need to deal with any of Stiring. It's faster and shorter.