BOJ 18830 하이퍼 수열과 하이퍼 쿼리

const int cdim = 11;
using v11 = array<int, cdim>;
v11 dim, sz;
int totSz;
vector<ll> A, pfsum;

int point_to_idx(const v11 &point){
    int idx = 0;
    rep(d, 0, cdim) idx += point[d] * sz[d];
    return idx;
}

vector<ll> make_prefix_sum(int cd = 0, v11 cp = {}){
    vector<ll> res;
    if(cd == cdim){
        int idx = point_to_idx(cp);
        res.push_back(A[idx]);
        return res;
    }

    rep(i, 0, dim[cd]){
        cp[cd] = i;
        vector<ll> tmp = make_prefix_sum(cd+1, cp);
        if(res.empty()) res = tmp;
        else{
            rep(j, 0, tmp.size()) res.push_back(res[(i-1) * sz[cd] + j] + tmp[j]);
        }
    }
    cp[cd] = 0;

    return res;
}

void solve(){
    rep(i, 0, cdim) cin >> dim[i];
    sz[cdim-1] = 1;
    rrep(d, cdim-1, 0) sz[d] = sz[d+1] * dim[d+1];
    totSz = sz[0] * dim[0];
    A.resize(totSz);
    pfsum.resize(totSz, 0);
    rep(i, 0, totSz) cin >> A[i];

    pfsum = make_prefix_sum();

    int Q; cin >> Q;
    while(Q--){
        v11 L, R;
        rep(d, 0, cdim) cin >> L[d];
        rep(d, 0, cdim) cin >> R[d];
        rep(d, 0, cdim) L[d]--, R[d]--;

        ll ans = 0;
        rep(mask, 0, (1<<cdim)){
            v11 point = R;
            bool add = true, flag = true;

            rep(d, 0, cdim) if(mask & (1<<d)){
                point[d] = L[d]-1;
                add = !add;
                if(point[d] < 0){
                    flag = false;
                    break;
                }
            }
            if(!flag) continue;

            int idx = point_to_idx(point);
            if(add) ans += pfsum[idx];
            else ans -= pfsum[idx];
        }
        cout << ans << "\n";
    }
}