백준 25213 - 조각 케이크 (Hard) [C++]

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

25213번: 조각 케이크 (Hard)

 

[알고리즘 분류]

Meet in the Middle

Combinatorics

Prefix Sum

 

 

Meet in the Middle을 공부하고 풀어본 문제다.

 

 

 몇 가지 관찰이 필요하다.

1. lcm(2~25)는 그렇게 크지 않으므로, 분모를 통일할 수 있다. (계산이 편해진다.)

2. 모든 크기의 조각들이 무한히 존재할 때, 이들을 잘 모아 케이크 한 판으로 만들기 위해서는 많아봤자 25조각이 필요하다.

2-1. 이를 완전탐색하기에는 가짓수가 너무 많다. MITM을 활용해 2~18 / 19~25로 나누어주면 된다.

3. 크기 \(x\)의 조각을 \(k\)개 사용하면 경우의 수는 당연하게도 \({}_{cnt[x]}C_k\)이다.

 

 이렇게 쓰고 나니 관찰이라고 할 것도 없는 것 같다.

 

 답을 출력할 때, ans % mod로 하면 틀리고 (ans + mod) % mod로 하니까 맞았다. 진짜 왜지?????

+추가) 누적합 배열에서 모듈러 연산이 들어가서 pf[R+1] - pf[L]은 음수가 될 수 있다. 그래서 음수 처리를 해줘야 한다.

#include <bits/stdc++.h>
#define X first
#define Y second
 
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
 
#define endl '\n'
 
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
 
const ll mod = 1e9 + 7;
 
 
ll gcd(ll x, ll y){
    while (y){
        ll tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}
 
ll lcm(ll x, ll y){
    return x * y / gcd(x, y);
}
 
 
ll getPow(ll a, ll x){
    ll ret = 1;
    while (x){
        if (x & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        x >>= 1;
    }
    return ret;
}
 
struct Node{
    ll now, num, c;
};
 
ll inv[27], cnt[27], p[27];
ll pf[2520000];
ll l;
int n;
deque<Node> dq;
 
 
ll nCr(ll x, ll r){
    if (x < r) return 0;
    if (r == 0) return 1;
    ll ret = 1;
    for (ll i=x;i>x-r;i--){
        ret *= i;
        ret %= mod;
    }
    for (ll i=1;i<=r;i++){
        ret *= inv[i];
        ret %= mod;
    }
    return ret;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    for (int i=1;i<=25;i++){
        inv[i] = getPow(i, mod - 2);
    }
 
    l = 1;
    for (int i=1;i<=25;i++){
        l = lcm(l, i);
    }
    for (int i=1;i<=25;i++){
        p[i] = l / i;
    }
 
    cin >> n;
    for (int i=0;i<n;i++){
        int k;
        cin >> k;
        cnt[k]++;
    }
 
    vector<pll> b;
    dq.push_back({0, 18, 1});
    while (!dq.empty()){
        Node q = dq.front();
        dq.pop_front();
        if (q.num == 25){
            b.emplace_back(q.now, q.c);
            continue;
        }
        for (ll i=0;i<26;i++){
            if (q.now + p[q.num + 1] * i > 101 * l / 100 || cnt[q.num + 1] < i) break;
            dq.push_back({q.now + p[q.num + 1] * i, q.num + 1, q.c * nCr(cnt[q.num + 1], i) % mod});
        }
    }
    sort(b.begin(), b.end());
    vector<ll> cx;
    for (int i=0;i<b.size();i++){
        pf[i + 1] = (pf[i] + b[i].Y) % mod;
        cx.push_back(b[i].X);
    }
 
    ll ans = 0;
    dq.clear();
    dq.push_back({0, 1, 1});
    while (!dq.empty()){
        Node q = dq.front();
        dq.pop_front();
        if (q.num == 18){
            ll L = upper_bound(cx.begin(), cx.end(), 99 * l / 100 - q.now - 1) - cx.begin();
            ll R = upper_bound(cx.begin(), cx.end(), 101 * l / 100 - q.now) - cx.begin() - 1;
            ans += (pf[R + 1] - pf[L]) * q.c % mod;
            ans %= mod;
            continue;
        }
        for (ll i=0;i<19;i++){
            if (q.now + p[q.num + 1] * i > 101 * l / 100 || cnt[q.num + 1] < i) break;
            dq.push_back({q.now + p[q.num + 1] * i, q.num + 1, q.c * nCr(cnt[q.num + 1], i) % mod});
        }
    }
    cout << (ans + mod) % mod << endl;
    return 0;
}