[Silver V] 자동차 주차 - 30993

[문제 위치]

https://www.acmicpc.net/problem/30993

[문제 풀이]
이 문제는 조합론(중복 원소가 있는 순열) 를 통해 해결하는 문제이다.
N칸에 빨강 A대, 초록 B대, 파랑 C대를 배치할 때 같은 색끼리는 구분하지 않으므로 경우의 수는 N!/(A!B!C!)이다. 단, 값이 매우 커질 수 있으므로 소수 분해(v_p(n!))로 각 소수의 지수를 e_p = v_p(N!) − v_p(A!) − v_p(B!) − v_p(C!)로 구한 뒤, 큰 정수(기수 10^9) 곱셈으로 ∏ p^{e_p}를 만들어 출력하게 해결한다
아래는 이를 구현한 코드이다.

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

// 큰 정수(양수) - 10^9 진법
struct BigInt {
    static const uint32_t BASE = 1000000000u;
    vector<uint32_t> d; // little-endian

    BigInt(uint64_t x = 0) { *this = x; }

    BigInt& operator=(uint64_t x){
        d.clear();
        if (x == 0) return *this;
        while (x){
            d.push_back(uint32_t(x % BASE));
            x /= BASE;
        }
        return *this;
    }

    bool isZero() const { return d.empty(); }

    void mul_uint(uint64_t m){ // 곱하는 수 m은 64비트 정수
        if (m == 1) return;
        if (m == 0 || isZero()){ d.clear(); return; }
        uint64_t carry = 0;
        for (size_t i = 0; i < d.size(); ++i){
            __uint128_t cur = (__uint128_t)d[i] * m + carry;
            d[i] = (uint32_t)(cur % BASE);
            carry = (uint64_t)(cur / BASE);
        }
        while (carry){
            d.push_back((uint32_t)(carry % BASE));
            carry /= BASE;
        }
    }

    string str() const {
        if (isZero()) return "0";
        stringstream ss;
        int n = (int)d.size();
        ss << d.back();
        for (int i = n - 2; i >= 0; --i){
            ss << setw(9) << setfill('0') << d[i];
        }
        return ss.str();
    }
};

// n 이하의 소수 나열(에라토스테네스)
vector<int> sieve(int n){
    vector<int> primes;
    vector<bool> comp(n + 1, false);
    for (int i = 2; i <= n; ++i){
        if (!comp[i]){
            primes.push_back(i);
            if ((long long)i * i <= n)
                for (long long j = 1LL * i * i; j <= n; j += i)
                    comp[(int)j] = true;
        }
    }
    return primes;
}

// v_p(n!) = sum_{k>=1} floor(n / p^k)
long long vp_fact(long long n, int p){
    long long r = 0;
    while (n){
        n /= p;
        r += n;
    }
    return r;
}

int main(){
    FASTIO;
    long long N, A, B, C;
    if (!(cin >> N >> A >> B >> C)) return 0;

    // 소수 분해로 지수 계산
    vector<int> primes = sieve((int)N);
    BigInt ans(1);

    for (int p : primes){
        long long e = vp_fact(N, p) - vp_fact(A, p) - vp_fact(B, p) - vp_fact(C, p);
        if (e <= 0) continue;

        // p^e 를 ans에 곱한다: 과도한 호출을 줄이기 위해 덩어리로 묶어서 곱함
        uint64_t chunk = 1;
        const uint64_t LIM = BigInt::BASE / 2; // 여유 있게
        while (e--){
            if (chunk > LIM / (uint64_t)p){
                ans.mul_uint(chunk);
                chunk = 1;
            }
            chunk *= (uint64_t)p;
        }
        if (chunk > 1) ans.mul_uint(chunk);
    }

    cout << ans.str() << '\n';
    return 0;
}