티스토리 뷰
11차원이라고 겁먹지 말자. 그냥 [] 가 11개 있을 뿐이다.
이번글에서는 반말을 사용하겠다. ㅇㅋ?
자 보면 걍 부분합 배열 채워서 쓱-싹 하면 되는 문제잖아 그치?
근데 포함-배제의 원리를 사용하면 시간초과가 나! (아이고 안타까워라)
그래서 새로운 방법으로 부분합 배열을 채울꺼야!
2차원 배열이 있다고 생각해보면
위에서 아래로 부분합을 한번 하고
왼쪽에서 오른쪽으로 부분합을 한번해!
그러면 부분합 배열이 만들어 지거든? (와 개쩐다;;)
이제 그러면 포함-배제의 원리를 이용하여 부분합 배열을 채우면 O(2048N) 으로 시간초과가 나지만
이제 11차원(우엑;;)으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알았다!
그래서 저 방법을 사용하면 O(11N) 으로 된다 이말이야! 짝짝짝짝짝
내가 코드를 좀 개같이 짜서 간단한 함수 설명을 할게
Do : 지금 쿼리가 a[ret[0][0]~ret[0][1]][ret[1][0]~ret[1][1]] ... [ret[10][0]~ret[10][1]] 일때 값 구하기 (아 몰라 대충 알아서 들어), 포함-배제의 원리를 사용하는 2차작업
f : 포함-배제의 원리를 사용하는 1차작업
이제 쿼리를 처리할때는 포함-배제의 원리를 사용해도 시간이 되니까 사용하고 ㅇㅇ!
Game Over
풀이 블로그에 코드가 없으면 섭하지?
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
int n[15],p[11],Q,F,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,ret[11][2],c[11]; //11차원
vector<vector<vector<vector<vector<vector<vector<vector<vector<vector<vector<ll>>>>>>>>>>> a;
ll Do() {
ll rett = 0;
do {
F = 0;
for(int i = 0;i < 11;i++) {
if(!p[i]) c[i] = ret[i][1];
else {
c[i] = ret[i][0]-1;
if(c[i] == -1) {
F = 1; break;
}
}
}
if(!F) rett += a[c[0]][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]][c[7]][c[8]][c[9]][c[10]];
}while(prev_permutation(p,p+11));
return rett;
}
ll f() {
ll rett = 0;
for(int i = 1;i <= 11;i++) {
memset(p,0,sizeof(p));
for(int j = 0;j < i;j++) p[j] = 1;
if(i % 2) rett += Do();
else rett -= Do();
}
return rett;
}
int main() {
for(int i = 1;i <= 11;i++) scanf("%d",&n[i]);
a.resize(n[1]);
for(i1 = 0;i1 < n[1];i1++) { a[i1].resize(n[2]);
for(i2 = 0;i2 < n[2];i2++) { a[i1][i2].resize(n[3]);
for(i3 = 0;i3 < n[3];i3++) { a[i1][i2][i3].resize(n[4]);
for(i4 = 0;i4 < n[4];i4++) { a[i1][i2][i3][i4].resize(n[5]);
for(i5 = 0;i5 < n[5];i5++) { a[i1][i2][i3][i4][i5].resize(n[6]);
for(i6 = 0;i6 < n[6];i6++) { a[i1][i2][i3][i4][i5][i6].resize(n[7]);
for(i7 = 0;i7 < n[7];i7++) { a[i1][i2][i3][i4][i5][i6][i7].resize(n[8]);
for(i8 = 0;i8 < n[8];i8++) { a[i1][i2][i3][i4][i5][i6][i7][i8].resize(n[9]);
for(i9 = 0;i9 < n[9];i9++) { a[i1][i2][i3][i4][i5][i6][i7][i8][i9].resize(n[10]);
for(i10 = 0;i10 < n[10];i10++) { a[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10].resize(n[11]);
for(i11 = 0;i11 < n[11];i11++) {
scanf("%lld",&a[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10][i11]);
}
}
}
}
}
}
}
}
}
}
}
for(int w = 0;w < 11;w++) {
memset(c,0,sizeof(c));
c[w] = 1;
for(i1 = 0,ret[0][1] = ret[0][0] = 0;i1 < n[1];ret[0][0]++,ret[0][1]++,i1++)
for(i2 = 0,ret[1][1] = ret[1][0] = 0;i2 < n[2];ret[1][0]++,ret[1][1]++,i2++)
for(i3 = 0,ret[2][1] = ret[2][0] = 0;i3 < n[3];ret[2][0]++,ret[2][1]++,i3++)
for(i4 = 0,ret[3][1] = ret[3][0] = 0;i4 < n[4];ret[3][0]++,ret[3][1]++,i4++)
for(i5 = 0,ret[4][1] = ret[4][0] = 0;i5 < n[5];ret[4][0]++,ret[4][1]++,i5++)
for(i6 = 0,ret[5][1] = ret[5][0] = 0;i6 < n[6];ret[5][0]++,ret[5][1]++,i6++)
for(i7 = 0,ret[6][1] = ret[6][0] = 0;i7 < n[7];ret[6][0]++,ret[6][1]++,i7++)
for(i8 = 0,ret[7][1] = ret[7][0] = 0;i8 < n[8];ret[7][0]++,ret[7][1]++,i8++)
for(i9 = 0,ret[8][1] = ret[8][0] = 0;i9 < n[9];ret[8][0]++,ret[8][1]++,i9++)
for(i10 = 0,ret[9][1] = ret[9][0] = 0;i10 < n[10];ret[9][0]++,ret[9][1]++,i10++)
for(i11 = 0,ret[10][1] = ret[10][0] = 0;i11 < n[11];ret[10][0]++,ret[10][1]++,i11++)
if(ret[w][1] != 0) a[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10][i11] += a[i1-c[0]][i2-c[1]][i3-c[2]][i4-c[3]][i5-c[4]][i6-c[5]][i7-c[6]][i8-c[7]][i9-c[8]][i10-c[9]][i11-c[10]];
}
scanf("%d",&Q);
while(Q--) {
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 11;j++) {
scanf("%d",&ret[j][i]); ret[j][i]--;
}
}
printf("%lld\n",a[ret[0][1]][ret[1][1]][ret[2][1]][ret[3][1]][ret[4][1]][ret[5][1]][ret[6][1]][ret[7][1]][ret[8][1]][ret[9][1]][ret[10][1]]-f());
}
return 0;
}