BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5)

1트컷해서 기분조음 :)

PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다.

하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다.

얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다.

prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다.

그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.)

 

다행히도 얘를 O(11 * nmopqrstuvw)에 채울 수 있다! 그건 바로 한 차원씩 누적하면 된다. 한 차원을 먼저 1차원 누적합으로 누적해놓으면, 차원이 하나 줄어든 prefix sum을 계산하면 되기 때문이라고 생각하면 편하다.

예시를 보자.

 

1 2 4

8 16 32

 

이 table에서 먼저 -> 방향으로 누적합을 구하면 이렇게 된다.

 

1 3 7

8 24 56

 

그리고 이 상태에서 ↓ 방향으로 누적합을 구하면 이렇게 된다.

 

1 3 7

9 27 63

 

그리고 이 결과는 원본 배열의 누적합과 정확히 동일한 결과이다. 어쨌든 결론은 이렇게 한 차원씩 훑으면 된다.

이제 쿼리만 처리하면 되는데, 쿼리는 4만 개이므로 포함배제로 계산해도 충분하다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll m,n,o,p,q,r,s,t,u,v,w;
#define V vector
#define VV vector<ll>
int main(){
    fast;
    cin>>m>>n>>o>>p>>q>>r>>s>>t>>u>>v>>w;
    V<V<V<V< V< V< V< V< V< V< V<ll> > > > > > > >>>> arr(m,V<V<V<V<V<V<V<V<V<V<ll>>>>>>>>>>(n,V<V<V<V<V<V<V<V<V<ll>>>>>>>>>(o,V<V<V<V<V<V<V<V<ll>>>>>>>>(p,V<V<V<V<V<V<V<ll>>>>>>>(q,V<V<V<V<V<V<ll>>>>>>(r,V<V<V<V<V<ll>>>>>(s,V<V<V<V<ll>>>>(t,V<V<V<ll>>>(u,V<V<ll>>(v,V<ll>(w)))))))))));
    for(int a = 0 ; a < m ; a++)for(int b = 0 ; b < n ; b++)for(int c = 0 ; c < o ; c++)for(int d = 0 ; d < p ; d++)for(int e = 0 ; e < q ; e++)for(int f = 0 ; f < r ; f++)for(int g = 0 ; g < s ; g++)for(int h = 0 ; h < t ; h++)for(int i = 0 ; i < u ; i++)for(int j = 0 ; j < v ; j++)for(int k = 0 ; k < w ; k++)cin>>arr[a][b][c][d][e][f][g][h][i][j][k];
    for(int I = 0 ; I < 11 ; I++){
        for(int a = 0 ; a < m ; a++)for(int b = 0 ; b < n ; b++)for(int c = 0 ; c < o ; c++)for(int d = 0 ; d < p ; d++)for(int e = 0 ; e < q ; e++)for(int f = 0 ; f < r ; f++)for(int g = 0 ; g < s ; g++)for(int h = 0 ; h < t ; h++)for(int i = 0 ; i < u ; i++)for(int j = 0 ; j < v ; j++)for(int k = 0 ; k < w ; k++){
            ll tmp[11]={};
            tmp[I]++;
            if(a+tmp[0]==m or b+tmp[1]==n or c+tmp[2]==o or d+tmp[3]==p or e+tmp[4]==q or f+tmp[5]==r or g+tmp[6]==s or h+tmp[7]==t or i+tmp[8]==u or j+tmp[9]==v or k+tmp[10]==w)continue;
            arr[a+tmp[0]][b+tmp[1]][c+tmp[2]][d+tmp[3]][e+tmp[4]][f+tmp[5]][g+tmp[6]][h+tmp[7]][i+tmp[8]][j+tmp[9]][k+tmp[10]] += arr[a][b][c][d][e][f][g][h][i][j][k];
        }
    }
    ll Q; cin>>Q;
    while(Q--){
        ll q1[11], q2[11];
        for(int i = 0 ; i < 11 ; i++)cin>>q1[i], q1[i]--;
        for(int j = 0 ; j < 11 ; j++)cin>>q2[j], q2[j]--;
        ll res = 0;
        for(int i = 0 ; i < (1<<11) ; i++){
            ll tmp[11]={};
            ll cnt = 0;
            ll IDX[11]={};
            bool flag=0;
            for(int j = 0 ; j < 11 ; j++){
                if(i&(1<<j))tmp[j]--, cnt++, IDX[j] = q1[j]-1;
                else IDX[j] = q2[j];
                if(IDX[j]<0){
                    flag=1;
                    break;
                }
            }
            if(flag)continue;
            res += arr[IDX[0]][IDX[1]][IDX[2]][IDX[3]][IDX[4]][IDX[5]][IDX[6]][IDX[7]][IDX[8]][IDX[9]][IDX[10]] * (cnt&1 ? -1 : 1);
        }
        cout<<res<<"\n";
    }
}

 

벡터 생성하는게 제일 어려웠다.