Bitset

📝 문제 정보 # 링크: 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/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.