Блог пользователя Ashik_01

Автор Ashik_01, история, 5 лет назад, По-английски

Can anyone plz help me with this problem?Problem

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Just precalculate all factorials in the range [0, 107] modulo 1000000000000037.

Then the rest is just range sum.

Edit. I tried it out. The answer is correct. But I didn't notice the memory limit (This solution will get MLE). Sorry.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Lets solve it offline. There are maximum 2*n different numbers. Calculate factorial only for this numbers. Notice that, when we multiplying the big numbers, there can exists number that  > 1023. So use binary multiplying.

    My Code
    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      You can use 1000-ary multiplication as given (mod = 10 ^15) * 10 ^ 3 < MAX_LONG_INT. It will cost maximum of only 3 operations reducing the log(n) factor.

      int base = 1000;
      LL mulmod(LL b, LL a, LL mod) { // (b * a) % mod
      	if(!b) return 0;
      	return ((mulmod(b/base, a, mod) * base ) % mod + (a * (b % base)) % mod) % mod;
      }