048.cpp

#include <iostream>
using namespace std;

typedef unsigned long long verylong;
class bigNmod
{
  verylong A, B;
public:
    bigNmod (unsigned k)
  {
    A = 0;
    B = k;
  }
  void square ()
  {
    verylong newB = B * B;
    verylong newA = A * B * 2 + newB / 100000;
    A = newA % 100000;
    B = newB % 100000;
  }
  void times (unsigned y)
  {
    B *= y;
    A = (A * y + B / 100000) % 100000;
    B %= 100000;
  }
  verylong value ()             //return the value of N
  {
    return A * 100000 + B;
  }
};

unsigned
small_term (unsigned k)         //used to calculate small terms
{
  unsigned answer = 1;
  for (int i = 1; i <= k; i++)
    answer *= k;
  return answer;
}

unsigned
reverse (unsigned k)            //needed to calculate power
{
  unsigned new_k = 1; //mark the end of binary string to be 1
  do
    {
      new_k <<= 1;
      if (k & 1) new_k++;
      k >>= 1;
    }
  while (k > 0);
  return new_k;
}

verylong
big_term (unsigned k)           //used to calculate large terms
{
  bigNmod answer (k);
  unsigned index = reverse (k);
  index >>= 1;
  do
    {
      answer.square ();
      if (index & 1)
          answer.times (k);

      index >>= 1;              //more efficient than index/=2
    }
  while (index > 1); //stop when the end bit has attained
  return answer.value ();
}

int
main ()
{
  verylong sum = 1;             //the 1st term
  for (unsigned k = 2; k <= 9; k++)     //2nd to 9th term
    sum += small_term (k);

  for (unsigned k = 11; k <= 999; k++)  //11th to 999th term
    {
      if (k % 10 == 0)
        continue;               //exclude multiples of 10
      sum += big_term (k);
    }
//verylong sum = big_term (11);
  cout  << (sum % 10000000000ULL)<< endl;
  return 0;
}