给定N，且ff（N）=f（1）+f（2）+..+f（N），其中f（k）是 由前k个自然数构成的集合的所有子集之和 .任务是找到ff（N）模100000007。 例如：
null
输入： 2. 输出： 7. f（1）+f（2） f（1）=1=1 f（2）=1+2+{1+2}=6 输入： 3. 输出： 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
方法 ：找到将要形成的序列模式。f（1）、f（2）、f（3）的值分别为1、6和31。让我们找到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.
因此ff（N）将是
ff(1) = f(1) = 1ff(2) = f(1) + f(2) = 7ff(3) = f(1) + f(2) + f(3) = 31ff(4) = f(1) + f(2) + f(3) + f(4) = 111...
形成的系列是1，7，31，111…存在一个公式 2^n*（n^2+n+2）–1 .式中，N从零开始。 以下是上述方法的实施情况。
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; } |
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 ) . "" ; // 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> |
输出：
111
时间复杂性： O（logn）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
