STFM - Editorial

PROBLEM LINK:

Practice
Contest

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

2 Likes

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

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.

1 Like

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 :smiley: 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 :smiley:

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

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

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

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

@himanshu_9419

It was all about Handling the overflow. :slight_smile:
Good one.

2 Likes

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

2 Likes

Awesome problem…

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

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

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

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.

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.

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!

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

2 Likes

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?

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…

//