5
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$ Apr 25 '15 at 17:54
  • \$\begingroup\$ @Daniel Sokolov I'm new to CR. I used to give answers in the SO style \$\endgroup\$
    – hindmost
    Apr 26 '15 at 8:39
  • \$\begingroup\$ @hindmost: Your answer is fine: it's normal to include model code in answers here at Code Review. \$\endgroup\$ Apr 28 '15 at 7:56
2
\$\begingroup\$

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

\$\endgroup\$
8
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Apr 25 '15 at 3:56
  • \$\begingroup\$ P.S. I do get right output \$\endgroup\$ Apr 25 '15 at 4:07
  • \$\begingroup\$ @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? \$\endgroup\$
    – hindmost
    Apr 25 '15 at 9:50
  • 1
    \$\begingroup\$ It is the same. Think of x*x! as (x+1-1)*x! which is (x+1)!-x!..Summing them up gives that expression \$\endgroup\$ Apr 25 '15 at 11:20
  • \$\begingroup\$ @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) \$\endgroup\$ Apr 25 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.