dsal 使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

原文:https://www . geeksforgeeks . org/product-of-all-sorted-size-子集-k-use-elements-what-index-divide-k-complete/

给定一个由 N 个不同元素组成的整数数组 arr[] ，以及一个正整数 K ( K < = N)。任务是从给定的数组中计算大小为 K 的所有排序子集的乘积，使用索引完全除以 K 的元素。

注意:由于答案可能非常大，以 10^9+7.为模打印

示例:

输入: arr[] = {4，7，5，9，3}，K = 4 输出: 808556639 解释: 在这种情况下有 5 个可能的集合: {4，7，5，9} - > 180(排序顺序{4，5，7，9}:索引 1，2，4 除 M，所以集合的值为 4 * 5 * 9 = 180) 3} - > 108 {4，7，5，3} - > 84 {7，5，9，3} - > 135 合计值=(180 * 108 * 108 * 84 * 135)%(10⁹+7)= 808556639

输入: arr[] = {7，8，9}，K = 2 输出: 254016

天真方法:

我们可以找到大小为 K 的所有子集，然后对子集进行排序，找到每个子集的值并相乘，得到最终的答案。由于可以有 2 个 ^N 子集，这种方法对于大的 N 值来说效率不是很高

有效方法:

其思想不是创建所有子集来寻找答案，而是计算所有子集内每个元素的计数。如果我们找到所有子集中每个元素的计数，那么答案将是

$\text{Final answer} = ((arr[1]^{(\text{count of arr[1]})}) * ((arr[2]^{(\text{count of arr[2]})})* ..... *((arr[N]^{(\text{count of arr[N]})})$

为了找到 arr[i]的计数，我们必须找到不同子集的总数，这些子集可以通过将 arr[i]放置在将 K 完全除的每个可能的索引处而形成。
通过将 arr[i]放置在第 j ^个索引处(j 完全除 K)形成的集合数将为:

^{(小于 arr[i]的元素总数)} C _j-1 * ^{(大于 arr[i]的元素总数)}C_k-jT10】

由于任何元素的计数都可能很大，所以要求(arr[I]^(arr[I]))%(10⁹+7)我们就要用到 费马小定理 也就是

{ a^(p-1)mod p = 1 } =>{(a^x)% p =(a^{(x % p-1)})% p。

所以，利用费马小定理

(arr[I]^(arr[I]))%(10⁹+7)=>(arr[I]^{(arr[I]% 109+6)})%(10⁹+7)。

下面是上述方法的实现:

C++

// C++ implementation of the above approach

#include <bits/stdc++.h>
using namespace std;
int p = 1000000007;

// Iterative Function to calculate
// (x^y)%p in O(log y)
long long int power(long long int x,
                    long long int y,
                    long long int p)
{
    long long int res = 1;
    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;
        x = (x * x) % p;
    }
    return res;
}

// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
void nCr(long long int n, long long int p,
         int f[][100], int m)
{

    for (long long int i = 0; i <= n; i++) {
        for (long long int j = 0; j <= m; j++) {

            // If j>i then C(i, j) = 0
            if (j > i) {
                f[i][j] = 0;
            }

            // If iis equal to j then
            // C(i, j) = 1
            else if (j == 0 || j == i) {
                f[i][j] = 1;
            }

            else {
                f[i][j] = (f[i - 1][j]
                           + f[i - 1][j - 1])
                          % p;
            }
        }
    }
}

// Function calculate the Final answer
void ProductOfSubsets(int arr[], int n,
                      int m)
{
    int f[n + 1][100];

    nCr(n, p - 1, f, m);

    sort(arr, arr + n);

    // Initialize ans
    long long int ans = 1;

    for (long long int i = 0; i < n; i++) {

        // x is count of occurence of arr[i]
        // in different set such that index
        // of arr[i] in those sets divides
        // K completely.
        long long int x = 0;

        for (long long int j = 1; j <= m; j++) {

            // Finding the count of arr[i] by
            // placing it at index which
            // divides K completely
            if (m % j == 0) {

                // By Fermat's theorem
                x = (x
                     + (f[n - i - 1][m - j]
                        * f[i][j - 1])
                           % (p - 1))
                    % (p - 1);
            }
        }

        ans
            = ((ans * power(arr[i], x, p)) % p);
    }

    cout << ans << endl;
}

// Driver code
int main()
{

    int arr[] = { 4, 5, 7, 9, 3 };
    int K = 4;

    int N = sizeof(arr) / sizeof(arr[0]);

    ProductOfSubsets(arr, N, K);

    return 0;
}

Java 语言(一种计算机语言，尤用于创建网站)

// Java implementation of the above approach
import java.util.*;

class GFG{
static int p = 1000000007;

// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {

        // If y is odd, multiply
        // x with result
        if (y % 2 == 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
static void nCr(int n, int p,
                int f[][], int m)
{
    for(int i = 0; i <= n; i++)
    {
       for(int j = 0; j <= m; j++)
       {

          // If j>i then C(i, j) = 0
          if (j > i)
          {
              f[i][j] = 0;
          }

          // If iis equal to j then
          // C(i, j) = 1
          else if (j == 0 || j == i)
          {
              f[i][j] = 1;
          }
          else
          {
              f[i][j] = (f[i - 1][j] +
                         f[i - 1][j - 1]) % p;
          }
       }
    }
}

// Function calculate the Final answer
static void ProductOfSubsets(int arr[], int n,
                                        int m)
{
    int [][]f = new int[n + 1][100];

    nCr(n, p - 1, f, m);
    Arrays.sort(arr);

    // Initialize ans
    long ans = 1;

    for(int i = 0; i < n; i++)
    {

       // x is count of occurence of arr[i]
       // in different set such that index
       // of arr[i] in those sets divides
       // K completely.
       int x = 0;

       for(int j = 1; j <= m; j++)
       {

          // Finding the count of arr[i] by
          // placing it at index which
          // divides K completely
          if (m % j == 0)
          {

              // By Fermat's theorem
              x = (x + (f[n - i - 1][m - j] *
                        f[i][j - 1]) %
                        (p - 1)) %
                        (p - 1);
          }
       }
       ans = ((ans * power(arr[i], x, p)) % p);
    }
    System.out.print(ans + "\n");
}

// Driver code
public static void main(String[] args)
{

    int arr[] = { 4, 5, 7, 9, 3 };
    int K = 4;
    int N = arr.length;

    ProductOfSubsets(arr, N, K);
}
}

// This code is contributed by Rajput-Ji

Python 3

# Python3 implementation of the above approach
p = 1000000007

# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p):
    res = 1
    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
        x = (x * x) % p

    return res

# Iterative Function to calculate
# (nCr)%p and save in f[n][r]
def nCr(n, p, f, m):

    for i in range(n + 1):
        for j in range(m + 1):

            # If j>i then C(i, j) = 0
            if (j > i):
                f[i][j] = 0

            # If i is equal to j then
            # C(i, j) = 1
            elif(j == 0 or j == i):
                f[i][j] = 1

            else:
                f[i][j] = (f[i - 1][j] +
                           f[i - 1][j - 1]) % p

# Function calculate the Final answer
def ProductOfSubsets(arr, n, m):

    f = [[0 for i in range(100)]
            for j in range(n + 1)]

    nCr(n, p - 1, f, m)
    arr.sort(reverse = False)

    # Initialize ans
    ans = 1

    for i in range(n):

        # x is count of occurence of arr[i]
        # in different set such that index
        # of arr[i] in those sets divides
        # K completely.
        x = 0

        for j in range(1, m + 1, 1):

            # Finding the count of arr[i] by
            # placing it at index which
            # divides K completely
            if (m % j == 0):

                # By Fermat's theorem
                x = ((x + (f[n - i - 1][m - j] *
                           f[i][j - 1]) %
                               (p - 1)) %
                               (p - 1))

        ans = ((ans * power(arr[i], x, p)) % p)

    print(ans)

# Driver code
if __name__ == '__main__':

    arr = [ 4, 5, 7, 9, 3 ]
    K = 4
    N = len(arr);

    ProductOfSubsets(arr, N, K)

# This code is contributed by samarth

C

// C# implementation of the above approach
using System;
class GFG{

static int p = 1000000007;

// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {

        // If y is odd, multiply
        // x with result
        if (y % 2 == 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Iterative Function to calculate
// (nCr)%p and save in f[n,r]
static void nCr(int n, int p,
                int [,]f, int m)
{
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {

            // If j>i then C(i, j) = 0
            if (j > i)
            {
                f[i, j] = 0;
            }

            // If iis equal to j then
            // C(i, j) = 1
            else if (j == 0 || j == i)
            {
                f[i, j] = 1;
            }
            else
            {
                f[i, j] = (f[i - 1, j] +
                           f[i - 1, j - 1]) % p;
            }
        }
    }
}

// Function calculate the Final answer
static void ProductOfSubsets(int []arr, int n,
                                        int m)
{
    int [,]f = new int[n + 1, 100];

    nCr(n, p - 1, f, m);
    Array.Sort(arr);

    // Initialize ans
    long ans = 1;

    for(int i = 0; i < n; i++)
    {

        // x is count of occurence of arr[i]
        // in different set such that index
        // of arr[i] in those sets divides
        // K completely.
        int x = 0;

        for(int j = 1; j <= m; j++)
        {

            // Finding the count of arr[i] by
            // placing it at index which
            // divides K completely
            if (m % j == 0)
            {

                // By Fermat's theorem
                x = (x + (f[n - i - 1, m - j] *
                          f[i, j - 1]) %
                              (p - 1)) %
                              (p - 1);
            }
        }
        ans = ((ans * power(arr[i], x, p)) % p);
    }
    Console.Write(ans + "\n");
}

// Driver code
public static void Main(String[] args)
{

    int []arr = { 4, 5, 7, 9, 3 };
    int K = 4;
    int N = arr.Length;

    ProductOfSubsets(arr, N, K);
}
}

// This code is contributed by Rajput-Ji

java 描述语言

<script>

// Javascript implementation
// for the above approach

let p = 1000000007;

// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p)
{
    let res = 1;
    x = x % p;
    while (y > 0)
    {

        // If y is odd, multiply
        // x with result
        if (y % 2 == 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// Iterative Function to calculate
// (nCr)%p and save in f[n][r]
function nCr(n, p, f, m)
{
    for(let i = 0; i <= n; i++)
    {
       for(let j = 0; j <= m; j++)
       {

          // If j>i then C(i, j) = 0
          if (j > i)
          {
              f[i][j] = 0;
          }

          // If iis equal to j then
          // C(i, j) = 1
          else if (j == 0 || j == i)
          {
              f[i][j] = 1;
          }
          else
          {
              f[i][j] = (f[i - 1][j] +
                         f[i - 1][j - 1]) % p;
          }
       }
    }
}

// Function calculate the Final answer
function ProductOfSubsets(arr, n, m)
{
    let f = new Array(n+1);
    for (var i = 0; i < f.length; i++) {
    f[i] = new Array(2);
    }

    nCr(n, p - 1, f, m);
    arr.sort();

    // Initialize ans
    let ans = 1;

    for(let i = 0; i < n; i++)
    {

       // x is count of occurence of arr[i]
       // in different set such that index
       // of arr[i] in those sets divides
       // K completely.
       let x = 0;

       for(let j = 1; j <= m; j++)
       {

          // Finding the count of arr[i] by
          // placing it at index which
          // divides K completely
          if (m % j == 0)
          {

              // By Fermat's theorem
              x = (x + (f[n - i - 1][m - j] *
                        f[i][j - 1]) %
                        (p - 1)) %
                        (p - 1);
          }
       }
       ans = ((ans * power(arr[i], x, p)) % p);
    }
    document.write(ans + "<br/>");
}

// Driver Code

    let arr = [ 4, 5, 7, 9, 3 ];
    let K = 4;
    let N = arr.length;

    ProductOfSubsets(arr, N, K);

</script>

Output:

808556639

时间复杂度: (N * K)

辅助空间:O(N * 100)T4】

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：http://www.moonapi.com/news/38847.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-11》

分类

最近更新

dsal 使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

C++

Java 语言(一种计算机语言，尤用于创建网站)

Python 3

C

java 描述语言

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-11》

dsal 使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

使用其索引完全划分 K 的元素的大小为 K 的所有排序子集的乘积

C++

Java 语言(一种计算机语言，尤用于创建网站)

Python 3

C

java 描述语言

留言

联系客服

dsal 查看更多书籍