给定一个由 n 个整数组成的数组 arr[] ，任务是从给定的数组中找出所有可能的对的乘积，例如:
- (arr[i]，arr[i]) 也被认为是有效对。
- (arr[i]、arr[j]) 和 (arr[j]、arr[i]) 被认为是两个不同的对。
打印结果答案模数 10^9 7.
示例:
输入: arr[] = {1，2} 输出: 16 解释: 所有有效对为(1，1)、(1，2)、(2，1)和(2，2)。 因此，1 * 1 * 1 * 2 * 2 * 1 * 2 * 2 = 16
输入: arr[] = {1，2，3} 输出: 46656 解释: 所有有效对为(1，1)，(1，2)，(1，3)，(2，1)，(2，2)，(2，3)，(3，1)，(3，2)和(3，3)。 因此该产品为 1 * 1 * 1 * * 2 * 1 * 3 * 2 * 1 * 2 * 2 * 2 * 3 * 3 * 1 * 3 * 2 * 3 * 3 = 46656
天真方法:解决上述问题的天真方法是找到所有可能的对，并计算每对元素的乘积。
下面是上述方法的实现:
c
// c implementation to find the
// product of all the pairs from
// the given array
#include
using namespace std;
#define mod 1000000007
// function to return the product of
// the elements of all possible pairs
// from the array
int productpairs(int arr[], int n)
{
// to store the required product
int product = 1;
// nested loop to calculate all
// possible pairs
for (int i = 0; i < n; i ) {
for (int j = 0; j < n; j ) {
// multiply the product of
// the elements of the
// current pair
product *= (arr[i] % mod
* arr[j] % mod)
% mod;
product = product % mod;
}
}
// return the final result
return product % mod;
}
// driver code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << productpairs(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to find the
// product of all the pairs from
// the given array
import java.util.*;
class gfg{
static final int mod = 1000000007;
// function to return the product of
// the elements of all possible pairs
// from the array
static int productpairs(int arr[], int n)
{
// to store the required product
int product = 1;
// nested loop to calculate all
// possible pairs
for(int i = 0; i < n; i )
{
for(int j = 0; j < n; j )
{
// multiply the product
// of the elements of the
// current pair
product *= (arr[i] % mod *
arr[j] % mod) % mod;
product = product % mod;
}
}
// return the final result
return product % mod;
}
// driver code
public static void main(string[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
system.out.print(productpairs(arr, n));
}
}
// this code is contributed by sapnasingh4991
python 3
# python3 implementation to find the
# product of all the pairs from
# the given array
mod = 1000000007;
# function to return the product of
# the elements of all possible pairs
# from the array
def productpairs(arr, n):
# to store the required product
product = 1;
# nested loop to calculate all
# possible pairs
for i in range(n):
for j in range(n):
# multiply the product
# of the elements of the
# current pair
product *= (arr[i] % mod *
arr[j] % mod) % mod;
product = product % mod;
# return the final result
return product % mod;
# driver code
if __name__ == '__main__':
arr = [1, 2, 3];
n = len(arr);
print(productpairs(arr, n));
# this code is contributed by 29ajaykumar
c
// c# implementation to find the
// product of all the pairs from
// the given array
using system;
class gfg{
static readonly int mod = 1000000007;
// function to return the product of
// the elements of all possible pairs
// from the array
static int productpairs(int []arr, int n)
{
// to store the required product
int product = 1;
// nested loop to calculate all
// possible pairs
for(int i = 0; i < n; i )
{
for(int j = 0; j < n; j )
{
// multiply the product
// of the elements of the
// current pair
product *= (arr[i] % mod *
arr[j] % mod) % mod;
product = product % mod;
}
}
// return the readonly result
return product % mod;
}
// driver code
public static void main(string[] args)
{
int []arr = { 1, 2, 3 };
int n = arr.length;
console.write(productpairs(arr, n));
}
}
// this code is contributed by sapnasingh4991
java 描述语言
output: 46656
时间复杂度: o(n 2 )
高效方法:我们可以观察到，每个元素作为一对 (x，y) 的元素之一，恰好出现 (2 * n) 次。正好 n 倍为 x ，正好 n 倍为 y 。
下面是上述方法的实现:
c
// c implementation to find the product
// of all the pairs from the given array
#include
using namespace std;
#define mod 1000000007
#define ll long long int
// function to calculate
// (x^y)00000007
int power(int x, unsigned int y)
{
int p = 1000000007;
// 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 result
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
// return the final result
return res;
}
// function to return the product
// of the elements of all possible
// pairs from the array
ll productpairs(ll arr[], ll n)
{
// to store the required product
ll product = 1;
// iterate for every element
// of the array
for (int i = 0; i < n; i ) {
// each element appears (2 * n) times
product
= (product
% mod
* (int)power(
arr[i], (2 * n))
% mod)
% mod;
}
return product % mod;
}
// driver code
int main()
{
ll arr[] = { 1, 2, 3 };
ll n = sizeof(arr) / sizeof(arr[0]);
cout << productpairs(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to find the product
// of all the pairs from the given array
import java.util.*;
class gfg{
static final int mod = 1000000007;
// function to calculate
// (x^y)00000007
static int power(int x, int y)
{
int p = 1000000007;
// 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 result
if (y % 2 == 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
// return the final result
return res;
}
// function to return the product
// of the elements of all possible
// pairs from the array
static int productpairs(int arr[], int n)
{
// to store the required product
int product = 1;
// iterate for every element
// of the array
for (int i = 0; i < n; i )
{
// each element appears (2 * n) times
product = (product % mod *
(int)power(arr[i],
(2 * n)) % mod) % mod;
}
return product % mod;
}
// driver code
public static void main(string[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
system.out.print(productpairs(arr, n));
}
}
// this code is contributed by amal kumar choubey
python 3
# python3 implementation to find the product
# of all the pairs from the given array
mod = 1000000007
# function to calculate
# (x^y)00000007
def power(x, y):
p = 1000000007
# initialize result
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 result
if ((y & 1) != 0):
res = (res * x) % p
y = y >> 1
x = (x * x) % p
# return the final result
return res
# function to return the product
# of the elements of all possible
# pairs from the array
def productpairs(arr, n):
# to store the required product
product = 1
# iterate for every element
# of the array
for i in range(n):
# each element appears (2 * n) times
product = (product % mod *
(int)(power(arr[i], (2 * n))) %
mod) % mod
return (product % mod)
# driver code
arr = [ 1, 2, 3 ]
n = len(arr)
print(productpairs(arr, n))
# this code is contributed by divyeshrabadiya07
c
// c# implementation to find the product
// of all the pairs from the given array
using system;
class gfg{
const int mod = 1000000007;
// function to calculate
// (x^y)00000007
static int power(int x, int y)
{
int p = 1000000007;
// 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 result
if (y % 2 == 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
// return the final result
return res;
}
// function to return the product
// of the elements of all possible
// pairs from the array
static int productpairs(int []arr, int n)
{
// to store the required product
int product = 1;
// iterate for every element
// of the array
for (int i = 0; i < n; i )
{
// each element appears (2 * n) times
product = (product % mod *
(int)power(arr[i],
(2 * n)) % mod) % mod;
}
return product % mod;
}
// driver code
public static void main()
{
int []arr = { 1, 2, 3 };
int n = arr.length;
console.write(productpairs(arr, n));
}
}
// this code is contributed by code_mech
java 描述语言
output: 46656
时间复杂度:t2【o(n)t4】
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
