STFM - Editorial

easy
editorial
feb15
math

#1

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

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*,m) + fact(L*,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


#3

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


#4

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


#5

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


#6

@himanshu_9419

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


#7

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


#8

Awesome problem…


#9

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


#10

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!


#11

Hi,

I have re-attempted this problem in C++ using the idea of precomputing all the factorial values until the value of M (maximum value of mod)…

However I’m getting WA on the last sub-task and also on 1st subtask of task 3:

#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

//We compute all the factorials up to the modulo max value
/* the product will contain M on it, which means its value will always be 0 mod M */
#define MAXFACT 19999999

long long int precalc[MAXFACT]={0LL};

void PreComputeModdedFactorials(int m)
{
	precalc[0]=1;
	for(int i = 1; i <= MAXFACT; i++)
		precalc* = (i%m*precalc[i-1]%m)%m;
}

long long int prodVal(unsigned long long int x)
{
	if(x<=MAXFACT)
	return precalc[x+1];
	else
	return 0;
}

long long int negval(int m)
{
	return m-1; // -1 mod M = M-1
}

long long int divparcel(unsigned long long int x, int m)
{
	if(x%2==0)
		return (x%m*(x/2)%m*(x+1)%m)%m;
	else
		return (x%m*x%m*((x+1)/2)%m)%m;
}

long long int f(unsigned long long int x, int m)
{
	return (((divparcel(x,m)%m+negval(m)%m)%m)+prodVal(x))%m;
}
	
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin >> n >> m;
	PreComputeModdedFactorials(m);
	vector<unsigned long long> v(n);
	for(int i = 0; i < n; i++)
		cin >> v*;
	
	unsigned long long ans = 0ULL;
	for(int i = 0; i < n; i++)
	{
		//cout << prodVal(v*) << endl;
		ans = (ans%m + f(v*, m)%m)%m;
	}
	cout << ans%m << endl;

	return 0;
}

In advance, sorry for the “mod spam”, but, besides that, is there anything wrong with the code? If yes, what? =))

Best,

Bruno


#12

Is this correct? To handle the divison parcel?

unsigned long long int divparcel(unsigned long long int x, int m)
{
	if(x%2==0)
		return (((x%m*(x/2)%m)%m)*(x+1)%m)%m;
	else
		return ((x%m*x%m)%m*((x+1)/2)%m)%m;
}

#13

WHAT IS WRONG IN MY CODE … I M NOT GETTING IT
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define size6 10000003
#define size5 100001

#define s(n) n=Scan_f()
#define loop(i,N) for(i=0;i<N;i++)
#define pll(n) printf("%lld
",n)

typedef long long int ulli;

inline unsigned long long int Scan_f()
{
int c;
do
c = fgetc(stdin);
while ( (c < ‘0’ || c > ‘9’) && c != EOF );

unsigned long long int a = 0;
while ( c >= '0' && c <= '9' )
{
    a = a*10 + (c - '0');
    c = fgetc(stdin);
}
return a;

}
ulli i,N,K,memofact[size6]= {0} ,memofinal[size6]= {0};
ulli fact(ulli n)
{
if(n==1) return 1;
{
ulli x;
if(memofact[n]!=0) return memofact[n];
{
x=(n*(fact(n-1)))%K;
memofact[n]=x;
return x;
}
}
}
ulli modulo(ulli n)
{
ulli y;
if(n%2==0)
{
y=n/2;
y%=K;
y*=((n+1)%K);
y%=K;
y*=((n)%K);
y%=K;

}
else
{
    {
        y=(n+1)/2;
        y%=K;
        y*=((n)%K);
        y%=K;
        y*=((n)%K);
        y%=K;
    }
}
return y;

}

ulli tag=10000;

ulli calc(ulli n)
{
if(n==1) return 2%K;
{
ulli x;
if(memofinal[n]!=0) return memofinal[n];
{
while(n>tag)
{
x=fact(tag);
tag+=1000;
}
ulli y;
x=(fact(n+1)-1)%K;
y=modulo(n);

        x=(x+y)%K;

        memofinal[n]=x;
        return x;
    }
}

}

int main()
{
memofact[1]=1;
s(N);
s(K);
// memofinal[0] fOR STOREING NO.
{
ulli ans=0;
{
loop(i,N)
{
s(memofinal[0]);
if(memofinal[0]>=(K-1))
ans=(ans+modulo(memofinal[0]))%K;
else
ans=(ans+calc(memofinal[0]))%K;
}
pll(ans);
}
}
return 0;
}


#14

please Explain this (i!=0, for i>=M)


#15

Good proof for 1∗1!+2∗2!+…+x∗x! = (x+1)!−1:

Let Sum = 1∗1!+2∗2!+…+x∗x!

Add (1! + 2! + … + x!) to both sides.

Sum + (1! + 2! + … + x!) = (1.1! + 1!) + (2.2! + 2!) + (3.3! + 3!) + … + (x.x! + x!)

Sum + (1! + 2! + … + x!) = (2!) + (3!) + (4!) + … + (x+1)!

Sum = (x+1)! - 1.


#16

please help me out. what is wrong in my code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll S1(ll x, ll m)
{
    if(x%2 == 0)
        return ((x/2)%m * x%m * (x+1)%m)%m;
    else
        return (x%m * x%m * ((x+1)/2)%m)%m;
}

ll S2(ll fact[], ll max, ll x, ll m)
{
    if(x <= max+1)
        return (fact[x+1]-1+m)%m;
    else
        return (m-1);
}

int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    ll p[n];
    ll max = 1;
    for(ll i=0;i<n;i++)
    {
         scanf("%lld",&p*);
         max = (max < p* && p* < m)?p*:max;
    }
    ll fact[max+2];
    fact[0] = 1;
    for(ll i=1;i<=max+1;i++)
        fact* = (fact[i-1]%m * i%m)%m;
    ll sum = 0;
    for(ll i=0;i<n;i++)
        sum = (sum%m + (S1(p*,m)%m + S2(fact,max,p*,m)%m)%m)%m;
    printf("%lld

",sum);
return 0;
}


#17

My solution is failing on test case 7. All other cases are passing. What might be the issue?
I am unable to figure this out.

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;

long long precompute[10000001];

// calculating i+1 ! in precompute*
void pre_compute(int m) {
    precompute[0] = 0;
    precompute[1] = 2;
    for (long long i = 2; i<m; i++) {
        precompute* = precompute[i-1]*(i+1);
        precompute* %= m;
    }
}

long long fun(long long x, int m) {
    long long ans = ((x%m) * ((x+1)%m))/2;
    ans %= m;
    ans *= (x%m);
    ans %= m;
    if (x > m)
        x = m-1;
    ans += (precompute[x] - 1);
    ans %= m;
    return ans;
}

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    pre_compute(m);
    long long temp;
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        scanf("%lld",&temp);
        sum += fun(temp, m);
        sum %= m;
    }
    printf("%lld

",sum);
return 0;
}


#18

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.


#19

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:


#20

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