# CodeChef- Chef and Strange Formula

For positive integer x let define function F(x) = 1 * (1! + x) + 2 * (2! + x) + .. + x * (x! + x).

"k!" means factorial: k! = 1 * 2 * .. * k

Chef wants to calculate F(p1) + F(p2) + ... + F(pn).

As answer could be large, help him, calculate value modulo m.

Input

First line contains two integers n and m. Next line contains n space separated integers pi.

Output

Output a single line containing one integer --- calculated value modulo m.

Constraints

1 ≤ n ≤ 10^5
1 ≤ pi ≤ 10^18
1 ≤ m ≤ 10^7


Subtask #1: 1 ≤ pi ≤ 6 (10 points)
Subtask #2: 1 ≤ pi ≤ 7 * 10^3 (25 points)
Subtask #3: m - prime number (25 points)
Subtask #4: original constraints (40 points)


Here is my code

#include <stdio.h>
#define M 10000000

long long int factorial(long long int n)
{
long long int i,fact=1;
for(i=1;i<=n;i++)
fact=((fact%M)*(i%M))%M;
return fact;
}
long long int func(long long int n)
{
long long int a=((n%M)*(n%M)*((n+1)%M))%M/2;
long long int sum=(a+factorial(n+1)-1)%M;
return sum;
}

int main()
{
long long int n,m;
scanf("%lld%lld",&n,&m);
long long int i,p[n];
for(i=0;i<n;i++)
{
scanf("%lld",&p[i]);
}
long long int sum=0;
for(i=0;i<n;i++)
{
sum+=func(p[i]);
}
printf("%lld\n",sum%m);
return 0;
}


My code exceeds time limit on subtasks 2,3 and 4. How do I improve efficiency?

As youself noted F(x) can be reduced to:

x*x*(x+1)/2 + (x+1)! - 1


As @Daniel Sokolov pointed, you don't need to calculate full factorial for each p[i]. If p is a sorted array, you can use previously calculated factorial in the current (x+1)! calculation.

Furthermore it would be better to get modulo after each arithmetic operation. This ensure that the current result after each operation will always < m*m < 10^14.

So the code might look like this:

/**
*  @param m modulo
*  @param n number of integers
*  @param p sorted array of integers
*  @return sum of F(pn) series modulo m
*/
function sum(unsigned long m, unsigned n, unsigned long long int *p) {
unsigned long long int
x, // current element of p array
x0 = 1, // previous element of p array
a, // sum of arithmetic progression
fac = 1, // factorial of (x + 1)
ret = 0; // result
for (unsigned i = 0; i < n; i++) {
x = p[i];
if (x < x0) return 0;
a = x % m * x % m * ((x + 1) / 2 % m) % m;
for (var k = x0 + 1; k <= x + 1; k++)
fac = fac * (k % m) % m;
ret = ((ret + a) % m + fac - 1) % m;
x0 = x;
}
return ret;
}


Note that it assumes p is a sorted array.

• Good point about p being a sorted array. I'm not sure that giving a complete code is the best answer format for this kind of question. After all, it's a challenge that Atul Shanbhag was trying to solve on it's own Apr 25 '15 at 17:54
• @Daniel Sokolov I'm new to CR. I used to give answers in the SO style Apr 26 '15 at 8:39
• @hindmost: Your answer is fine: it's normal to include model code in answers here at Code Review. Apr 28 '15 at 7:56

This looks like a dynamic programming exercise to me. You should store values of already calculated factorials. Then, you can do n! = (n-1)!*n and save the time waisted in the for loop.

P.S.

I'm not sure why you use modulo M everywhere in your solution. The problem is asking you to calculate the formula and give a result as modulo M

• The function F(x) = 1*1!+2*2!+...xx! can be further reduced to ( xx*(x+1) )/2+(x+1)!-1 and I'm taking modulus by M because x could be 10^18 so trying to reduce it down Apr 25 '15 at 3:56
• P.S. I do get right output Apr 25 '15 at 4:07
• @Atul Shanbhag Can you clarify how you get xx*(x+1)/2+(x+1)!-1 from the F(x) definition? I understand that xx*(x+1)/2 is a sum of arithmetic progression. But how you get (x+1)!-1? I think it should be: 1 + 2*2! + ... + x*x! which is not the same as (x+1)!-1. Isn't it? Apr 25 '15 at 9:50
• It is the same. Think of x*x! as (x+1-1)*x! which is (x+1)!-x!..Summing them up gives that expression Apr 25 '15 at 11:20
• @AtulShanbhag, How does it help you with the original problem of having to calculate the factorial for every p[i], though? If you stored the results for say f(4) globally, you could use that result when calculating f(6) Apr 25 '15 at 11:52