Inclusion_And_Exclusion

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/35108 🧐 관찰 및 접근 # $N$이 2500이니까 뭔가 제곱로그?까진 돌지 않을까 싶다. 음, 어떻게 잡으면 좋을지 모르겠지만, 저 주어진 게국지 그래프에서 안쪽의 네모중 왼쪽 위부터 반시계방향으로 $1, 2, 3, 4$ 라고 하면, $2, 4$번 정점을 기준으로 카운팅하고싶게 생기긴 했다. 일단 예제 그래프를 그려보자. ![[Drawing 2026-03-07 09.54.26.excalidraw.png]] 여기서 저 게국지모양을 찾아야 하는데… $1, 2, 3, 4$를 기7준으로 하면 $1, 2, 4$에 $5, 7, 6$을 붙이거나, $6, 7, 5$를 연결하는 두가지가 있겠다. 어.. 정점을 기준으로 세려고 하니 좀 까다로운거 같기도..? 그러면 간선을 기준으로..? 그러면 아무래도 양쪽에 날개가 붙어있는 간선으로 생각하자. 크아아아악 이래도 안되는데 일단 두 간선을 골라서 사이클을 고정시키는건 맞는거같다. 잉 이러면 걍 포함배제로 되는거 아닌가? 그러면 두 정점에 중복되는 정점, 세 정점에 중복되는 정점 뭐 그런게 필요한거같은데… 비트셋으로 하면 될라나? $O(M^2N/64)$ 정도인거같은데;; 일단 짜보자 좀 빡빡하다. 전처리를 잘 하면 시간 내로 들어간다. Clang이 훨 빠르네. 왜지? 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<pii> edges; vector<bitset<2500>> con(N); rep(i, 0, M){ int u, v; cin >> u >> v; u--; v--; edges.push_back({u, v}); con[u][v] = 1; con[v][u] = 1; } vector<ll> cnt1(N); rep(i, 0, N) cnt1[i] = con[i].count(); vector<vector<bitset<2500>>> con2(N, vector<bitset<2500>>(N)); rep(i, 0, N) rep(j, i+1, N) con2[i][j] = con2[j][i] = con[i]&con[j]; vector<vector<ll>> cnt2(N, vector<ll>(N)); rep(i, 0, N) rep(j, i+1, N) cnt2[i][j] = cnt2[j][i] = con2[i][j].count(); auto calc = [&](int v1, int v2, int v3, int v4) -> ll { auto &b1 = con[v1], &b2 = con[v2], &b3 = con[v3]; ll n1 = cnt1[v1] - (con[v1][v2] + con[v1][v3] + con[v1][v4]); ll n2 = cnt1[v2] - (con[v2][v1] + con[v2][v3] + con[v2][v4]); ll n3 = cnt1[v3] - (con[v3][v1] + con[v3][v2] + con[v3][v4]); ll n12 = cnt2[v1][v2] - (con2[v1][v2][v3] + con2[v1][v2][v4]); ll n23 = cnt2[v2][v3] - (con2[v2][v3][v1] + con2[v2][v3][v4]); ll n31 = cnt2[v3][v1] - (con2[v3][v1][v2] + con2[v3][v1][v4]); bitset<2500> b123 = b1&b2&b3; ll n123 = b123.count() - b123[v4]; return n1*n2*n3 - (n12*n3 + n23*n1 + n31*n2) + 2*n123; }; ll ans = 0; rep(i, 0, M) rep(j, i+1, M){ auto [a, b] = edges[i]; auto [c, d] = edges[j]; if(a == c || a == d || b == c || b == d) continue; if((!con[a][c] || !con[b][d]) && (!con[a][d] || !con[b][c])) continue; ll ret = 0; ret += calc(a, b, c, d); ret += calc(b, c, d, a); ret += calc(c, d, a, b); ret += calc(d, a, b, c); if(con[a][c] && con[b][d]) ans += ret; if(con[a][d] && con[b][c]) ans += ret; } cout << ans/2; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18830 🧐 관찰 및 접근 # 11차원인게 조금 이슈이므로, 간단하게 3차원정도로 생각해보자. 2차원이면 그냥 누적합 배열에서 $S(a_2, b_2) - S(a_1, b_2) - S(a_2, b_1) + S(a_1, b_1)$이었던 것이 기억난다. $a_1, b_1, c_1, a_2, b_2, c_2$가 주어진다. $a_1 \leq \alpha \leq a_2, b_1 \leq \beta \leq b_2, c_1 \leq \gamma \leq c_2$ 인 어쩌구에 대해 합을 출력한다. 이를 누적합으로 생각하면, $S(a_2, b_2, c_2) - S(a_1, b_2, c_2) - S(a_2, b_1, c_2) - S(a_2, b_2, c_1) + S(a_1, b_1, c_2) + S(a_1, b_2, c_1) + S(a_2, b_1, c_1) - S(a_1, b_1, c_1)$ 인 것 같다! 아님말고 암튼 $n$차원일때 누적합 배열을 구해둔다면 $2^n$의 시간복잡도로 계산할 수 있는 것 같다. 쿼리가 4만개이므로 $40000 * 2048 = 81920000$이므로 충분히 돌 것 같다. 그런데 누적합 배열을 만드는게 $O(2^n * mno...w)$ 라서 이게 20억인데… 포함배제로 구하지 말고, 차원에 대해서 구하고 밀어버리자. 💻 풀이 # 코드 (C++): 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"; } } 🔒 구현 코드 잠금