C. On Number of Decompositions into Multipliers

경우의 수(중복조합), 순열


출처: Codeforces C. On Number of Decompositions into Multipliers

sol)
들어 오는 a1, a2, ---, an 각각을 소인수 분해하여 map에 저장한다.
ex) mm[5] = 2는 5^2을 나타낸다.
map을 쭉 순회하면서 각 소인수가 있는 횟수를 이용하여
중복조합 계산을한다.
ex) mm[5] = 2 5가 2개 있고 n개의 자리에 뿌려주는 방법
이것은 중복조합이다.
서로다른 n개를 r개 뽑는 가지 수

순열을 계산할 때 오버플로가 날 수 있으니 Division modulo를 써야한다.
(a/b) mod prime = a * (b^(prime-2) % prime) % prime


[-] Collapse

#include<stdio.h>
#include<math.h>
#include<map>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

map<ll, ll> mm;
ll power(ll a, ll b) {
    ll pow = 1;
    while (b){
        if (b & 1){
            pow = (pow * a) % mod;
            --b;
        }
        a = (a*a) % mod;
        b = b / 2;
    }
    return pow;
}
ll comb(ll r, ll n){
    ll ans = 1;
    ll h = n + r - 1;
    for (ll c = h, p = 1 ; p <= r; c--, p++)
        ans = (((ans * c) %mod) * (power(p,mod-2) % mod)) % mod;
    return ans;
}

void factorize(ll v){
    for (ll i = 2; i*i <= v;){
        if (v % i == 0){
            mm[i]++;
            v /= i;
        }
        else i++;
    }
    if (v > 1) mm[v]++;
    return;
}
int main(){
    //freopen("input.txt", "r", stdin);
    ll n; scanf("%lld", &n);
    for (ll i = 0; i < n; i++){
        ll v; scanf("%lld", &v);
        if (v != 1) factorize(v);
    }
    map<ll, ll>::iterator it = mm.begin();
    ll ans = 1;
    while (it != mm.end()){
        ll c = it->second;
        ans *= (comb(c, n)%mod);
        ans %= mod;
        it++;
    }
    printf("%lld", ans);
    return 0;
}