Array yang Hilang

Soal#

Informasi#

• Sumber: CompFest 9 - Penyisihan CPC Senior
• Tanggal: 2017-08-12

Arsip#

• TLX

Ringkasan#

Carilah banyaknya array $X$ yang berisi $N$ bilangan bulat, sehingga $X_1 \cdot X_2 \cdot \ldots \cdot X_N$ bernilai sama dengan $A_1 \cdot A_2 \cdot A_3 \cdot \ldots \cdot A_N$! Jawaban dimodulo dengan $10^9 + 7$.

Solusi#

Petunjuk#

Pembahasan#

Mari kita cari faktorisasi prima dari $A_1 \cdot A_2 \cdot A_3 \cdot \ldots \cdot A_N$. Kita tidak perlu mengalikan semua bilangan tersebut. Kita bisa melakukan faktorisasi prima pada setiap bilangan, kemudian menjumlahkan eksponen dari setiap faktor prima yang sama. Berikut adalah contoh kode untuk melakukannya.

for(int i = 0; i < N; i++){
    for(int j = 2; j * j <= A[i]; j++){
        while(A[i] % j == 0){
            cnt[j]++;
            A[i] /= j;
        }
    }
    if(A[i] != 1) cnt[A[i]]++;
}

Array cnt menyimpan eksponen untuk setiap faktor prima. Dengan kata lain, $\text{cnt}[p_i] = e_i$.

Kemudian untuk setiap faktor prima $p_i$ yang berjumlah $e_i$, kita cari banyaknya cara untuk "mendistribusikannya" ke dalam array $X$. Teknik stars and bars dapat digunakan dalam kasus ini. Kita bisa bayangkan $N - 1$ pemisah yang akan memisahkan sebanyak $e_i$ faktor prima $p_i$ yang saling berjajar. Oleh karena itu, banyaknya cara untuk menyusun $N - 1$ pemisah adalah $\binom{e_i \ + \ N \ - \ 1}{N \ - \ 1} = \binom{e_i \ + \ N \ - \ 1}{e_i}$. Kemudian, kita kalikan banyaknya cara tersebut untuk semua faktor prima yang mungkin.

Kode#

#include <iostream>
using namespace std;
typedef long long int lli;

const lli MOD = 1E9 + 7;

lli T, N, Ai, ans;
lli cnt[100001];
lli F[2000001];
lli invers[2000001];
lli iF[2000001];

// Binomial coefficient
// n!/(r! * (n - r)!) = (1/r! * 1/(n - r)! * n!)
lli C(lli n, lli r){
    return ((iF[r] * iF[n - r]) % MOD * F[n] % MOD) % MOD;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // Precompute factorials (F[]) and the modular multiplicative inverse (iF[])
    F[0] = invers[0] = iF[0] = 1;
    for(lli i = 1; i <= 2000000; i++){
        F[i] = (i * F[i - 1]) % MOD;
        // https://cp-algorithms.com/algebra/module-inverse.html#finding-the-modular-inverse-for-prime-moduli-using-euclidean-division
        invers[i] = (i == 1 ? 1 : (MOD - ((MOD/i) * invers[MOD % i]) % MOD));
        iF[i] = (invers[i] * iF[i - 1]) % MOD;
    }

    cin >> T;
    while(T--){
        for(int i = 0; i <= 100000; i++)
            cnt[i] = 0;

        cin >> N;
        for(int i = 0; i < N; i++){
            cin >> Ai;
            for(int j = 2; j * j <= Ai; j++){
                while(Ai % j == 0){
                    cnt[j]++;
                    Ai /= j;
                }
            }
            if(Ai != 1) cnt[Ai]++;
        }

        ans = 1;
        for(lli i = 0; i <= 100000; i++)
            if(cnt[i])
                ans = (ans * C(cnt[i] + N - 1, cnt[i])) % MOD;

        cout << ans << '\n';
    }
    return 0;
}

Akhir Kata#

Saya baru sadar bahwa saya melakukan prekomputasi faktorial sebanyak $2 \cdot 10^6$, bukan sebanyak $2 \cdot 10^5$.