Find sum of product of number in given series

0 0 6 minutes read

Given two numbers N and T where, $1\leq N\leq 10000000000$ and $1\leq T \leq 1000$ . The task is to find the value of $sum = \sum_{i=1}^{i=N}\prod_{j=1}^{j=T} (i+j)$ .
Since sum can be large, output it modulo 10⁹+7.
Examples:

Input : 3 2
Output : 38
2*3 + 3*4 + 4*5 = 38

Input : 4 2
Output : 68

In the Given Sample Case n = 3 and t = 2.
sum = 2*3+3*4+4*5.
Notice that:
$1*2 = \frac{2!}{0!}$
$2*3 = \frac{3!}{1!}$
$3*4 = \frac{4!}{2!}$
$4*5 = \frac{5!}{3!}$

So each term is of the form    $\frac{x!}{(x-t)!}$
If we multiply and divide by t! it becomes   $t!*\frac{x!}{(x-t)!*t!}$
Which is nothing but   $t!*\;_{t}^{x}\textrm{C}$
Therefore, $sum = t!\;*\;\sum_{x=t+1}^{n+t}\; _{t}^{x}\textrm{C}$
But we know   $\sum_{x=t}^{N}\;_{t}^{x}\textrm{C}\;=\;_{t+1}^{N+1}\textrm{C}$
Therefore   $\sum_{x=t+1}^{n+t} _{k}^{x}\textrm{C}\; =\; _{t+1}^{n+t+1}\textrm{C}-1$
So final expression comes out to be   $t!*\;_{t+1}^{n+t+1}\textrm{C}-t!$
But since n is so large we can not calculate it directly, we have to Simplify the above expression.
On Simplifying we get   $\frac{\prod_{i=1}^{t+1}*(n+i)}{t+1} - t!$ .
Below is the implementation of above approach

C++

// C++ program to find sum of product 
// of number in given series
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const long long MOD = 1000000007;
 
// function to calculate (a^b)%p
ll power(ll x, unsigned long long y, ll p)
{
    ll res = 1; // Initialize result
 
    // Update x if it is more than or equal to p
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
ll sumProd(ll n, ll t)
{
    // modulo inverse of denominator
    ll dino = power(t + 1, MOD - 2, MOD);
 
    // calculating commentator part
    unsigned long long ans = 1;
    for (ll i = n + t + 1; i > n; --i)
        ans = (ans % MOD * i % MOD) % MOD;
 
    // calculating t!
    ll tfact = 1;
    for (int i = 1; i <= t; ++i)
        tfact = (tfact * i) % MOD;
 
    // accumulating the final answer
    ans = ans * dino - tfact + MOD;
 
    return ans % MOD;
}
int main()
{
    ll n = 3, t = 2;
 
    // function call to print required sum
    cout << sumProd(n, t);
 
    return 0;
}

Java

// Java program to find sum of product 
// of number in given series
 
public class GFG {
 
     static long MOD = 1000000007;
      
    //function to calculate (a^b)%p
     static long power(long x, long y, long p)
     {
      long res = 1; // Initialize result
 
      // Update x if it is more than or equal to p
      x = x % p;
 
      while (y > 0) {
 
          // If y is odd, multiply x with result
          if ((y & 1)!= 0)
              res = (res * x) % p;
 
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
      }
 
      return res;
     }
 
     //function to return required answer
     static long sumProd(long n, long t)
     {
      // modulo inverse of denominator
      long dino = power(t + 1, MOD - 2, MOD);
 
      // calculating commentator part
      long ans = 1;
      for (long i = n + t + 1; i > n; --i)
          ans = (ans % MOD * i % MOD) % MOD;
 
      // calculating t!
      long tfact = 1;
      for (int i = 1; i <= t; ++i)
          tfact = (tfact * i) % MOD;
 
      // accumulating the final answer
      ans = ans * dino - tfact + MOD;
 
      return ans % MOD;
     }
 
     // Driver program
    public static void main(String[] args) {
         
        long n = 3, t = 2;
 
         // function call to print required sum
         System.out.println(sumProd(n, t));
    }
}

Python3

# Python 3 program to find sum of product 
# of number in given series 
 
MOD = 1000000007
 
# function to calculate (a^b)%p
def power(x, y, p) :
 
    # Initialize result
    res = 1
 
    # Update x if it is more than or equal to p
    x = x % p
 
    # If y is odd, multiply x with result 
    while y > 0 :
 
        if y & 1 :
            res = (res * x) % p
 
        #  y must be even now
        y = y >> 1 # y = y/2
        x = (x * x) % p
 
    return res
 
# function to return required answer
def sumProd(n, t) :
 
    # modulo inverse of denominator 
    dino = power(t + 1, MOD - 2, MOD)
 
    ans = 1
 
    # calculating commentator part 
    for i in range(n + t + 1 , n, -1) :
        ans = (ans % MOD * i % MOD) % MOD
 
    # calculating t! 
    tfact = 1
    for i in range(1, t+1) :
        tfact = (tfact * i) % MOD
 
    # accumulating the final answer 
    ans = ans * dino - tfact + MOD
 
    return ans % MOD
             
     
# Driver Code
if __name__ == "__main__" :
 
    n, t = 3, 2
 
    # function call to print required sum 
    print(sumProd(n, t))
 
# This code is contributed by ANKITRAI1

C#

// C# program to find sum of product 
// of number in given series
using System;
class GFG 
{
static long MOD = 1000000007;
 
// function to calculate (a^b)%p
static long power(long x, long y, 
                  long p)
{
    long res = 1; // Initialize result
     
    // Update x if it is more
    // than or equal to p
    x = x % p;
     
    while (y > 0) 
    {
     
        // If y is odd, multiply x 
        // with result
        if ((y & 1) != 0)
            res = (res * x) % p;
     
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
static long sumProd(long n, long t)
{
     
// modulo inverse of denominator
long dino = power(t + 1, MOD - 2, MOD);
 
// calculating commentator part
long ans = 1;
for (long i = n + t + 1; i > n; --i)
    ans = (ans % MOD * i % MOD) % MOD;
 
// calculating t!
long tfact = 1;
for (int i = 1; i <= t; ++i)
    tfact = (tfact * i) % MOD;
 
// accumulating the final answer
ans = ans * dino - tfact + MOD;
 
return ans % MOD;
}
 
// Driver Code
public static void Main() 
{
    long n = 3, t = 2;
 
    // function call to print required sum
    Console.WriteLine(sumProd(n, t));
}
}
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to find sum of product 
// of number in given series
 
// function to calculate (a^b)%p
function power($x, $y, $p)
{
    $res = 1; // Initialize result
 
    // Update x if it is more 
    // than or equal to p
    $x = $x % $p;
 
    while ($y > 0) 
    {
 
        // If y is odd, multiply 
        // x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        $y = $y >> 1; // y = y/2
        $x = ($x * $x) % $p;
    }
 
    return $res;
}
 
// function to return required answer
function sumProd($n, $t)
{
    $MOD = 1000000007;
     
    // modulo inverse of denominator
    $dino = power($t + 1, $MOD - 2, $MOD);
 
    // calculating commentator part
    $ans = 1;
    for ($i = $n + $t + 1; $i > $n; --$i)
        $ans = ($ans % $MOD * $i % 
                       $MOD) % $MOD;
 
    // calculating t!
    $tfact = 1;
    for ($i = 1; $i <= $t; ++$i)
        $tfact = ($tfact * $i) % $MOD;
 
    // accumulating the final answer
    $ans = $ans * $dino - $tfact + $MOD;
 
    return $ans % $MOD;
}
 
// Driver code
$n = 3;
$t = 2;
 
// function call to print
// required sum
echo sumProd($n, $t);
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
 
// Javascript program to find sum of product 
// of number in given series
var MOD = 100000007;
 
// function to calculate (a^b)%p
function power(x, y, p)
{
    var res = 1; // Initialize result
 
    // Update x if it is more than or equal to p
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
function sumProd(n, t)
{
    // modulo inverse of denominator
    var dino = power(t + 1, MOD - 2, MOD);
 
    // calculating commentator part
    var ans = 1;
    for (var i = n + t + 1; i > n; --i)
        ans = (ans % MOD * i % MOD) % MOD;
 
    // calculating t!
    var tfact = 1;
    for (var i = 1; i <= t; ++i)
        tfact = (tfact * i) % MOD;
 
    // accumulating the final answer
    ans = ans * dino - tfact + MOD;
 
    return ans % MOD;
}
 
 
var n = 3, t = 2;
// function call to print required sum
document.write( sumProd(n, t));
 
// This code is contributed by noob2000.
</script>

Output:

Time Complexity: O(n+t)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!