E. Counting Arrays

Solution Approach

• Initially, calculate get_primes and get_factorials once.
• After taking input from the user we check for all the get_primes number such that the multiplication comes out to be x with y number of elements.
• After getting one such set we permute it with total number of ways to represent y-factorizations i.e. add negative sign if possible.
• We keep count for each permutation possible and finally return the count.

C++ implementation

/* C++ implementation of E. counting arrays */
#include <iostream>
#include <vector>

using namespace std;

/* Calculating get_primes and get_factorials once in starting in main code */
vector<int> get_primes(int n) {
    vector<char> prime;
    for (int i = 0; i != n + 1; i += 1) {
     prime.push_back(true);   
    }
    prime[1] = false;
    prime[0] = false;
    for (int i = 2; i <= n; i += 1) {
        if (prime[i]) {
            if (i * i <= n) {
                for (int j = i*i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i != prime.size(); i += 1) {
        if (prime[i]) {
            ans.push_back(i);
        }
    }
    return ans;
}

/* Calculating get_primes and get_factorials once in starting in main code */
vector<int> get_factorials(int n, int mod) {
    vector<int> res = {1};
    res.reserve(2e6);
    for (int i = 1; i != n + 1; ++i) {
        res.push_back((res[i - 1] * i) % mod);
    }
    return res;
}

/* All possible permutation of integers */
int binpow(int a, int n, int mod) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return (binpow(a, n - 1, mod) * a) % mod;
    }
    return binpow((a * a) % mod, n / 2, mod);
}

int bin_coef(int n, int k, vector<int>& factorials, vector<int>& op_factorials, int mod) {
    return (
        (
            (
                factorials[n] * op_factorials[k]
            ) % mod 
        ) * op_factorials[n - k]
    ) % mod;
}

vector<int> factorization(int n, vector<int>& primes) {
    vector<int> res;
    res.reserve(20);
    for (int i = 0; primes[i] * primes[i] <= n; i += 1) {
        if (n % primes[i] != 0) {
            continue;
        }
        int exp = 0;
        while (n % primes[i] == 0) {
            exp += 1;
            n /= primes[i];
        }
        res.push_back(exp);
    }
    if (n > 1){
        res.push_back(1);
    }
    return res;
}

/* Main function to counting arrays */
int solve(int x, int y, vector<int>& primes, vector<int>& factorials, vector<int>& op_factorials, int mod) {
    
    auto exps = factorization(x, primes);
    int ans = 1;
    
    for (int i = 0; i != exps.size(); i += 1) {
        ans *= bin_coef(
            y + exps[i] - 1, 
            exps[i], 
            factorials,
            op_factorials,
            mod
        );
        ans %= mod;
    }
    ans = (ans * binpow(2, y - 1, mod)) % mod;
    return ans;
}

/* Main Code */
signed main() {
    /* Given modulo condition to print in the question */
    const int mod = 1e9 + 7;
    auto primes = get_primes(2000);
    auto factorials = get_factorials(2000000, mod);
    vector<int> op_factorials;
    op_factorials.reserve(factorials.size());
    for (auto val : factorials) {
        op_factorials.push_back(binpow(val, mod - 2, mod));
    }

    int q;
    /* Taking number of test cases as input from user */
    cin >> q;
    /* Running while loop to run q test cases as given in E. counting arrays problem */
    while (q--) {
        int x, y;
        /* Taking x and y input as given in E. counting arrays problem */
        cin >> x >> y;
        /* Main function to counting arrays */
        int res = solve(x, y, primes, factorials, op_factorials, mod);
        cout << res << "\n";
    }
}

Input

2
6 3
4 2

Output

36
6

Complexities

Time complexity

O(x²y)
Reason: Two nested loops are required of size x. One loop of y is called in the function binpow function, so the time complexity is O(x²y)

Space complexity

O(n), where n is the given modulo in the problem statement.
Reason: We have used the push_back operation while running the binpow function so that the space complexity will be O(n).

Frequently Asked Questions

1. In C++, what is an array?
   An array is a sort of data structure in C++ that allows you to store multiple values of the same type.
    
2. How are arrays classified?
   Because they hold elements of the same type, arrays are categorized as homogenous data structures. In a single array, we can't have primitive data types together. On the other hand, arrays can contain unique numbers, strings, boolean values (true and false), characters, objects, and so on.
    
3. What is the purpose of an array?
   Arrays are best for storing several values in a single variable and processing a large number of values quickly. Using the indices, we can quickly retrieve the array elements. In any programming language, arrays are the most commonly used data type.
    
4. In C, what is array decay?
   Array decay is the loss of an array's type and dimensions. It happens when we use a pointer or a value to send an array into a function. The array receives the initial address, which is a pointer. As a result, the array's size differs from the original.
    
5. In C++, how do you pass an array by reference?
   A whole array cannot be passed as an argument to a function in C++. You can, however, supply a pointer to an array without an index by specifying the array's name.

Key Takeaways

In this article, we have solved the E. counting arrays problem using C++ language. We hope that this question will help you understand the concept of how to create an array with a given number of elements and the product of all elements.

Recommended problems -

• Product Array Puzzle
• Beautiful Array

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!