grinding_codexp's blog

1^k + 2^k + ... + n^k using Faulhaber's formula
By grinding_codexp, history, 2 hours ago, In English

I want to ask about this problem: 622F - The Sum of the k-th Powers. I solved it using lagrange interpolation 263080914 but can anyone help me implement the solution with Faulhaber's formula? Thanks very much.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
55 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

It's not easy to calculate the `Bernoulli number'. Also, the modulo is not NTT friendly.

→ Reply
  • »
    »
    52 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Consider these blogs: Prefix Sum Polynomial, and Counting sums of powers for "How to generate Bernoulli number".

    → Reply