Dado N, y ff(N) = f(1) + f(2) + …… + f(N), donde f(k) es la suma de todos los subconjuntos de un conjunto formado por los primeros k números naturales . La tarea es encontrar ff(N) módulo 1000000007.
Ejemplos:
Entrada: 2
Salida: 7
f(1) + f(2)
f(1) = 1 = 1
f(2) = 1 + 2 + {1 + 2} = 6
Entrada: 3
Salida: 31
f(1) + f(2) + f(3)
f(1) = 1 = 1
f(2) = 1 + 2 + {1 + 2} = 6
f(3) = 1 + 2 + 3 + {1 + 2} + {2 + 3} + {1 + 3} + {1 + 2 + 3} = 24
Planteamiento : Encuentra un patrón de la secuencia que se formará. Los valores de f(1), f(2), f(3) son 1, 6 y 31 respectivamente. Encontremos f(4).
f(4) = 1 + 2 + 3 + 4 + {1 + 2} + {1 + 3} + {1 + 4}
+ {2 + 3} + {2 + 4} + {3 + 4} + {1 + 2 + 3} + {1 + 2 + 4}
+ {1 + 3 + 4} + {2 + 3 + 4} + {1 + 2 + 3 + 4} = 80.
Por lo tanto ff(N) será
ff(1) = f(1) = 1 ff(2) = f(1) + f(2) = 7 ff(3) = f(1) + f(2) + f(3) = 31 ff(4) = f(1) + f(2) + f(3) + f(4) = 111 . . .
La serie formada es 1, 7, 31, 111… Existe una fórmula para ello que es 2^n*(n^2 + n + 2) – 1 . donde, N comienza desde cero.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
#include <bits/stdc++.h>
using namespace std;
// modulo value
#define mod (int)(1e9 + 7)
// Iterative Function to calculate (x^y)%p in O(log y)
int power(int x, int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0) {
// If y is odd, multiply x with the 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 find ff(n)
int check(int n)
{
// In formula n is starting from zero
n--;
// calculate answer using
// formula 2^n*(n^2 + n + 2) - 1
int ans = n * n;
// whenever answer is greater than
// or equals to mod then modulo it.
if (ans >= mod)
ans %= mod;
ans += n + 2;
if (ans >= mod)
ans %= mod;
ans = (power(2, n, mod) % mod * ans % mod) % mod;
// adding modulo while subtraction is very necessary
// otherwise it will cause wrong answer
ans = (ans - 1 + mod) % mod;
return ans;
}
// Driver code
int main()
{
int n = 4;
// function call
cout << check(n) << endl;
return 0;
}
C
// C program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
#include <stdio.h>
// modulo value
#define mod (int)(1e9 + 7)
// Iterative Function to calculate (x^y)%p in O(log y)
int power(int x, int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0) {
// If y is odd, multiply x with the 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 find ff(n)
int check(int n)
{
// In formula n is starting from zero
n--;
// calculate answer using
// formula 2^n*(n^2 + n + 2) - 1
int ans = n * n;
// whenever answer is greater than
// or equals to mod then modulo it.
if (ans >= mod)
ans %= mod;
ans += n + 2;
if (ans >= mod)
ans %= mod;
ans = (power(2, n, mod) % mod * ans % mod) % mod;
// adding modulo while subtraction is very necessary
// otherwise it will cause wrong answer
ans = (ans - 1 + mod) % mod;
return ans;
}
// Driver code
int main()
{
int n = 4;
// function call
printf("%d\n",check(n));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
class Geeks {
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x
// with the result
if (y != 0)
res = (res * x) % p;
// y must be even now
// y = y / 2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// function to find ff(n)
static int check(int n)
{
// modulo value
int mod = (int)(1e9 + 7);
// In formula n is
// starting from zero
n--;
// calculate answer using
// formula 2^n*(n^2 + n + 2) - 1
int ans = n * n;
// whenever answer is greater than
// or equals to mod then modulo it.
if (ans >= mod)
ans %= mod;
ans += n + 2;
if (ans >= mod)
ans %= mod;
ans = (power(2, n, mod) % mod *
ans % mod) % mod;
// adding modulo while subtraction
// is very necessary otherwise it
// will cause wrong answer
ans = (ans - 1 + mod) % mod;
return ans;
}
// Driver Code
public static void main(String args[])
{
int n = 4;
// function call
System.out.println(check(n));
}
}
// This code is contributed by ankita_saini
Python3
#Python3 program to find Sum of all # subsets of a set formed by # first N natural numbers | Set-2 # modulo value mod = (int)(1e9 + 7) # Iterative Function to calculate (x^y)%p in O(log y) def power(x,y,p): res = 1 # Initialize result x = x % p # Update x if it is more than or # equal to p while (y > 0): # If y is odd, multiply x with the 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 find ff(n) def check(n): # In formula n is starting from zero n=n-1 # calculate answer using # formula 2^n*(n^2 + n + 2) - 1 ans = n * n # whenever answer is greater than # or equals to mod then modulo it. if (ans >= mod): ans %= mod ans += n + 2 if (ans >= mod): ans %= mod ans = (pow(2, n, mod) % mod * ans % mod) % mod # adding modulo while subtraction is very necessary # otherwise it will cause wrong answer ans = (ans - 1 + mod) % mod return ans #Driver code if __name__=='__main__': n = 4 # function call print(check(n)) # This code is contributed by ash264
C#
// C# program to find Sum
// of all subsets of a set
// formed by first N natural
// numbers | Set-2
using System;
class GFG
{
// Iterative Function
// to calculate (x^y)%p
// in O(log y)
static int power(int x, int y,
int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with the result
if (y != 0)
res = (res * x) % p;
// y must be even
// now y = y / 2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// function to find ff(n)
static int check(int n)
{
// modulo value
int mod = (int)(1e9 + 7);
// In formula n is
// starting from zero
n--;
// calculate answer
// using formula
// 2^n*(n^2 + n + 2) - 1
int ans = n * n;
// whenever answer is
// greater than or equals
// to mod then modulo it.
if (ans >= mod)
ans %= mod;
ans += n + 2;
if (ans >= mod)
ans %= mod;
ans = (power(2, n, mod) % mod *
ans % mod) % mod;
// adding modulo while
// subtraction is very
// necessary otherwise it
// will cause wrong answer
ans = (ans - 1 + mod) % mod;
return ans;
}
// Driver Code
public static void Main(String []args)
{
int n = 4;
// function call
Console.WriteLine(check(n));
}
}
// This code is contributed
// by ankita_saini
PHP
<?php
// PHP program to find Sum
// of all subsets of a set
// formed by first N natural
// numbers | Set-2
// modulo value
// Iterative Function to
// calculate (x^y)%p in O(log y)
function power($x, $y, $p)
{
$res = 1; // Initialize result
$x = $x % $p; // Update x if it
// is more than or
// equal to p
while ($y > 0)
{
// If y is odd, multiply
// x with the 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 find ff(n)
function check($n)
{
$mod = 1e9+7;
// In formula n is
// starting from zero
$n--;
// calculate answer using
// formula 2^n*(n^2 + n + 2) - 1
$ans = $n * $n;
// whenever answer is greater
// than or equals to mod then
// modulo it.
if ($ans >= $mod)
$ans %= $mod;
$ans += $n + 2;
if ($ans >= $mod)
$ans %= $mod;
$ans = (power(2, $n, $mod) %
$mod * $ans %
$mod) % $mod;
// adding modulo while subtraction
// is very necessary otherwise it
// will cause wrong answer
$ans = ($ans - 1 + $mod) % $mod;
return $ans;
}
// Driver code
$n = 4;
// function call
echo check($n) ."\n";
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// javascript program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
// modulo value
const mod = (1e9 + 7);
// Iterative Function to calculate (x^y)%p in O(log y)
function power( x, y, p)
{
let res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with the 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 find ff(n)
function check( n)
{
// In formula n is starting from zero
n--;
// calculate answer using
// formula 2^n*(n^2 + n + 2) - 1
let ans = n * n;
// whenever answer is greater than
// or equals to mod then modulo it.
if (ans >= mod)
ans %= mod;
ans += n + 2;
if (ans >= mod)
ans %= mod;
ans = (power(2, n, mod) % mod * ans % mod) % mod;
// adding modulo while subtraction is very necessary
// otherwise it will cause wrong answer
ans = (ans - 1 + mod) % mod;
return ans;
}
// Driver code
let n = 4;
// function call
document.write(check(n));
// This code is contributed by aashish1995
</script>
Producción:
111
Complejidad temporal: O(log n).
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA