 # STFM - Editorial

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

1 Like

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

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

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!

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)…

#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=1;
for(int i = 1; i <= MAXFACT; i++)
precalc[i] = (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[i];

unsigned long long ans = 0ULL;
for(int i = 0; i < n; i++)
{
//cout << prodVal(v[i]) << endl;
ans = (ans%m + f(v[i], 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

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

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",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;
s(N);
s(K);
// memofinal fOR STOREING NO.
{
ulli ans=0;
{
loop(i,N)
{
s(memofinal);
if(memofinal>=(K-1))
ans=(ans+modulo(memofinal))%K;
else
ans=(ans+calc(memofinal))%K;
}
pll(ans);
}
}
return 0;
}

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

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.

1 Like

#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[i]);
max = (max < p[i] && p[i] < m)?p[i]:max;
}
ll fact[max+2];
fact = 1;
for(ll i=1;i<=max+1;i++)
fact[i] = (fact[i-1]%m * i%m)%m;
ll sum = 0;
for(ll i=0;i<n;i++)
sum = (sum%m + (S1(p[i],m)%m + S2(fact,max,p[i],m)%m)%m)%m;
printf("%lld\n",sum);
return 0;
}

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;

// calculating i+1 ! in precompute[i]
void pre_compute(int m) {
precompute = 0;
precompute = 2;
for (long long i = 2; i<m; i++) {
precompute[i] = precompute[i-1]*(i+1);
precompute[i] %= 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\n",sum);
return 0;
}

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 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 @Kuruma, No you don’t need to use CRT for passing the last subtask.