STFM - Editorial

elfus · February 9, 2015, 7:57pm

PROBLEM LINK:

Author: Antoniuk Vasyl
Tester: Pushkar Mishra
Editorialist: Florin Chirica

PROBLEM

Calculate the given sum.

QUICK EXPLANATION

Let F(x) = (1 * 1! + 2 * 2! + .... + x * x!) + (1 * x + 2 * x + .... + x * x)

For the first bracket, it’s enough to calculate up to M, because i * i! = 0, for i \ge M.
For the second bracket, we can use well known formula that 1 + 2 + ... + x = \frac{x (x + 1)}{2} We need to perform division before considering modulo operation.

EXPLANATION

Breaking the sum into two parts

When dealing with sums, a good idea is to “break” it. We can write F(x) as

F(x) = (1 * 1! + 2 * 2! + .... + x * x!) + (1 * x + 2 * x + .... + x * x)

The sums still look complicated. The trick here is to use the fact that modulo is reasonably small. Let’s calculate each bracket independently.

Sum of i * i!

Let’s recall definition of i!. i! = 1 * 2 * ... * i What happens if i \ge M (the modulo)? Then, obviously, term M will appear in the product. Since we calculate the expression modulo M, it’s like adding 0 element to the product (0 is equal to M modulo M). So, i! = 0, for i >= M. It immediately follows that i * i! = 0, for i \ge M.

Let’s store the sum of 1 * 1! + 2 * 2! + .... x * x! for each x \le M. We can compute it in \mathbb{O}(M). For each x \ge M, sum 1 * 1! + 2 * 2! + ... + x * x! is exactly 1 * 1! + 2 * 2! + ... + (M-1) * (M-1)!, since all the other terms are 0.

Alternatively, one can notice that 1 * 1! + 2 * 2! + ... + x * x! = (x+1)! - 1. This can easily be proven by mathematical induction.

Sum of i * x

Sum 1 * x + 2 * x + ... + x * x is in fact x * (1 + 2 + ... + x). We know that 1 + 2 + ... + x = \frac{x (x + 1)}{2}. So we get that the sum is \frac{x^2 \, (x + 1)}{2}. Since numbers x are up to 10^{18}, we might have a problem with the overflow. Moreover, we have to handle division by 2 somehow.

Let’s handle division by 2 firstly. One of the numbers x and x + 1 will be even. This means we can divide it by 2. Now the task is reduced to multiply 3 numbers, which can be up to 10^{18}.

We can use modulo properties once again. We know that (A * B) \,mod\, M = ((A\, mod\, M) * (B\, mod\, M))\, mod\, M. This means, we can reduce the task to multiply 3 numbers up to 10^7 (the modulo value) by doing modulo M for each of the numbers before multiplication.

This step is computed in \mathbb{O}(1), so the total complexity is \mathbb{O}(M + N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

Setter’s solution

kuruma · February 16, 2015, 3:37pm

Hi,

I attempted it in Python and got TLE and NZEC…

Used a similar idea I guess…

from math import *

def quoti(x,m):
	return ((x*x*x + x*x)/2)%m

def fact(x,m):
	return reduce(lambda x,y: (x*y)%m , [i for i in range(1,x+2)])

def negterm(m):
	return m-1
	
n,m = map(int, raw_input().split())
L = map(int,raw_input().split())

ans = 0
for i in range(n):
	#print ans
	ans += (quoti(L[i],m) + fact(L[i],m) + negterm(m))

print int(ans%m)

Any help?

I know that the above code could not be of use for the larger sub-tasks but, with some tweaks maybe it would pass the 1st and 2nd subtasks…

Did we need to use the Totient Function to compute the modular inverse of 2 modulo M if M was not a prime number? How could/should we approach this?

I was at a loss at this and the editorial is not very clear really…

Best,

Bruno

dpraveen · February 16, 2015, 3:40pm

I am just wondering whether complexity of your solution is \mathcal{O}(n^2). The calculation of fact seems like taking \mathcal{O}(n) for each iteration. I am not completely sure about this as I don’t understand the lambda syntax of python.

kuruma · February 16, 2015, 4:03pm

Hi @dpraveen, good catch, maybe that’s an issue… I will try to switch to C++ and use some factorial pre-processing of some sort to see if it’s possible to pass the first and second subtasks like that Thanks!! Also, is it something extra needed to pass the last subtask?
EDIT; nvm re-read the editorial, found the trick which was missing me! Nice one

dpraveen · February 16, 2015, 4:08pm

@Kuruma, No you don’t need to use CRT for passing the last subtask.

sherwin21990 · February 16, 2015, 4:40pm

What is the significance of sub task 3 where m is a prime number?

himanshu_9419 · February 16, 2015, 5:04pm

I’m getting wrong answer but I’m unable to find out any mistake in code or logic.

#include<stdio.h>
int main()
{
long long int n,m,p,ans=0,k,factorial=1,i,l;
scanf("%lld %lld",&n,&m);
while(n>0)
{
scanf("%lld",&p);
if((p+1%m==0)||(p%m==0)){ans+=-1; }
else {
for(i=2;i<=p;i++) {i%=m; factorial=(factorial*i)%m;}
ans+=((p+1)*factorial)%m+(((p*p*(p+1))/2))%m-1;
}
n--;
}
if(ans<0)ans+=m;
printf("%lld",(ans%m));
return 0;

}

Plz check the code

chhristov · February 16, 2015, 5:45pm

Why O(M+N) when there are N integers each requiring M operations? so M * N?

shivam9753 · February 16, 2015, 6:00pm

@himanshu_9419

It was all about Handling the overflow.
Good one.

shivam9753 · February 16, 2015, 6:10pm

You cannot just simply carry out the remainder of ((10^9)*(10^9)) divided by m.
Here’s the code snippet for mod of multiplication of such large values.

unsigned long long mulmod(unsigned long long a,unsigned long long b,unsigned long long c){
if(a<=1000000000ULL && b<=1000000000ULL){
unsigned long long ret = ((a%c)*(b%c))%c;
return ret;
}
unsigned long long ret = 0ULL;
a=a%c;
while(b > 0ULL){
if(b&1ULL) {
ret = (ret+a)%c;
}
a = (a<<1ULL)%c;
b>>=1ULL;
}
return ret%c;
}##

Heading

angad_singh95 · February 16, 2015, 6:16pm

Awesome problem…

the_darklord · February 16, 2015, 7:09pm

Let’s store the sum of 1∗1!+2∗2!+…x∗x! for each x≤M. We can compute it in O(M).

Can you tell me how can you compute this where m = 10,000,000

rahul_nexus · February 16, 2015, 7:34pm

Can you please elaborate your doubt? What part you did not understand?

arun_as · February 16, 2015, 7:47pm

You should ask your question as an actual question in the Forum. You most probably won’t get an answer if you post your question as an answer to another question

vikky_codder · February 16, 2015, 8:29pm

to calculate ( a / b ) % m you need to find multiplicative inverse of 2 modulo m and to calculate that m and b must me coprime.

rccroshan1 · February 16, 2015, 10:41pm

As said above (AB)%M=((A%M)(B%M)%M)…so lets consider a case where we need to calculate the factorial of 5.What we will do is calculate the factorial and perform the modulo operation on it.

fact=1; for i=1 to i<=5: fact=((fact%M)*(i%M))M; do it this way and you will get the correct answer.
Note : M here being the number whose modulo the answer should be.

tao_of_coding · February 16, 2015, 11:11pm

I am also having trouble seeing how computing each i*i! up to 10**7 is possible in time allowance. I understand each iteration is a single additional multiplication, but even the following is timing out for me at 5+ seconds:

import time
s = time.clock()
for i in range(10**7):
    x = i*i
print(time.clock()-s)

It seems that the ‘alternative’ formula (x+1)!-1 is completely necessary? No? Thanks!

xellos0 · February 16, 2015, 11:14pm

Maybe you just shouldn’t use Python for 10^7 operations. Slow languages are slow.

tao_of_coding · February 16, 2015, 11:31pm

Then maybe they shouldn’t allow it, or (preferably) they should accommodate for it…I am learning, and only 1 language at a time…

Also, I think that even with the alternative formula, the timing problem is the same, as (x+1)! is still same number of multiplications…

So problem is impossible for python? Is that the answer?

rccroshan1 · February 16, 2015, 11:31pm

You dont need to calculate 107…instead you need to calculate (107)%M for the given M and its not a big deal to calculate (10**7)%M…