Ashik_01's blog

By Ashik_01, history, 8 months ago, In English,

Can anyone plz help me with this problem?Problem

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Ashik_01 (previous revision, new revision, compare).

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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
    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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;
      }