Encuentra la suma del producto del número en una serie dada

Posted on by Rudeus Greyrat

Dados dos números N y T donde,  1\leq N\leq 10000000000 y  1\leq T \leq 1000 . La tarea es encontrar el valor de  suma = \sum_{i=1}^{i=N}\prod_{j=1}^{j=T} (i+j) .
Dado que la suma puede ser grande, imprímala módulo 10 9 +7 .
Ejemplos: 
 

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

Input : 4 2
Output : 68

En el caso de muestra dado n = 3 y t = 2 .
suma = 2*3+3*4+4*5 . 
Darse cuenta de: 
1*2 = \frac{2!}{0!}
2*3 = \frac{3!}{1!}
3*4 = \frac{4!}{2!}
4*5 = \frac{5!}{3!}

Así que cada término tiene la forma    \frac{x!}{(xt)!}
Si multiplicamos y dividimos por t! se convierte en   t!*\frac{x!}{(xt)!*t!}
Cuál no es nada más   que t!*\;_{t}^{x}\textrm{C}
Por lo tanto,  sum = t!\;*\;\sum_{x=t+1}^{n+t}\; _{t}^{x}\textrm{C}
Pero sabemos   \sum_{x=t}^{N}\;_{t}^{x}\textrm{C}\;=\;_{t+1}^{N+1}\textrm{C}
Por   lo tanto \sum_{x=t+1}^{n+t} _{k}^{x}\textrm{C}\; =\; _{t+1}^{n+t+1}\textrm{C}-1
Así que la expresión final resulta ser   t!*\;_{t+1}^{n+t+1}\textrm{C}-t!
Pero como n es tan grande que no podemos calcularlo directamente, tenemos que Simplificar la expresión anterior.
Al simplificar obtenemos   \frac{\prod_{i=1}^{t+1}*(n+i)}{t+1} - t! .
A continuación se muestra la implementación del enfoque anterior. 
 

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>

Producción: 

38

Complejidad del tiempo: O(T)
 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *