CodeChef- Chef and Strange Formula

Question

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

Subtasks

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?

Answer 1

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.

• Daniel Sokolov: 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
• hindmost: @Daniel Sokolov I'm new to CR. I used to give answers in the SO style
• Gareth Rees: @hindmost: Your answer is fine: it's normal to include model code in answers here at Code Review.

Answer 2

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

• Atul Shanbhag: 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
• Atul Shanbhag: P.S. I do get right output
• hindmost: @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?
• Atul Shanbhag: It is the same. Think of x*x! as (x+1-1)*x! which is (x+1)!-x!..Summing them up gives that expression
• Daniel Sokolov: @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)