UmCaraLegal's blog

Sum of Powers of natural numbers
By UmCaraLegal, history, 7 years ago, In English

Be F(N, K) = 1^k + 2^k + 3^k + ... + n^k.

Given N and K we need to calculate F(N, K) (mod 2^32)

INPUT:

1 <= N, K < 2^32

PS: I think about this question for a few days and didn't get success if you have any idea how to solve it, please share it :D

The problem can be found here to submit (statement in portuguese): http://olimpiada.ic.unicamp.br/pratique/programacao/nivels/2013f3p2_somapot

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

»
7 years ago, # |
← Rev. 6   Vote: I like it +10 Vote: I do not like it

Here's a similar question with editorial from HackerRank , unfortunately in the editorial the solution run in O(k), and probably will not pass here. I don't have a solution yet (i tried a lot too), but maybe this can help somehow. The solution presented in the editorial uses modular inverse and this will be a problem to consider too.

btw , expected time limit is 1 sec according to judge.

PS : Someone correct me if i'm wrong, but using Lagrange Polynomial or Bernoulli Numbers for solve this is out of question since B(2) don't have any inverse mod 2^32 and one can prove that same thing can happen with Lagrange Polynomial for sure for some values of K.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +59 Vote: I do not like it

If k < 32, use matrix exponentiation.

If k ≥ 32,

1k + ... + nk

and it reduces to the previous case.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why did you replace with ? But even then, I can't see how to evaluate mod 2^32.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Since j is small ( < 32) you can "walk on the line" of the pascal triangle.

      You can cancel the 2's that show up in denominator with the ones that appear on the numerator.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I am not sure, cancelling the 2's is fine but that doesn't mean the intermediate values will fit in the available data types. I am guessing you keep cancelling the 2's and take modulo inverses, is that correct?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          To be clearer, my idea is to remove all 2 factors from the divisors and calculate the multiplicative inverse with extended Euclid algorithm.

          Not sure if that is the most elegant way, but it'll do it.

          → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The most straightforward way is to use BigInteger.

      (Since j is small, is not too big.)

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate how to find binomial coefficients fast mod 2^32 and how to use matrix multiplication here? Thanks.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Write

      Convert this to matrix and use exponentation.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Awesome! Very clever trick to exploit the relation between summations removing the first, not the last element. Thanks!

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, i understand now.

        → Reply