알파카컵 1회: J - 알파카의 별빛 목장
루비 V의견: 0
알파카 왕국에는 일직선 모양의 별빛 목장이 있다. 목장은 \(1\)번 위치부터 \(L\)번 위치까지의 정수 좌표로 이루어져 있다.
이 목장에는 총 \(N\)개의 목초지가 있으며, 각 목초지는 서로 다른 위치에 존재한다. \(i\)번째 목초지는 위치 \(x_i\)에 있고, 색 \(c_i\)를 가진다.
알파카 사제들은 세 목초지를 골라 별빛 의식을 진행하려고 한다.
세 목초지 \(a, b, c\)가 다음 조건을 모두 만족하면, 이 세 목초지는 아름다운 별빛 목초지 삼중쌍이라고 한다.
1. 세 목초지의 위치가 증가하는 순서이다.
$$ x_a < x_b < x_c $$
2. 가운데 목초지가 정확히 양끝 목초지의 중앙에 있다. 즉, 세 목초지의 위치가 등차수열을 이룬다.
$$ x_b - x_a = x_c - x_b $$
3. 세 목초지의 색이 모두 서로 다르다. (\(c_a, c_b, c_c\)가 모두 서로 다름)
알파카 왕은 아름다운 별빛 목초지 삼중쌍의 개수를 알고 싶어 한다. 조건을 만족하는 삼중쌍의 개수를 구하시오.
- \(1 \le N \le 200{,}000\)
- \(1 \le L \le 200{,}000\)
- \(3 \le C \le 30\)
- \(1 \le x_i \le L\)
- \(1 \le c_i \le C\)
- \(x_i\)는 서로 다르다.
- 답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 세 정수 \(N\), \(L\), \(C\)가 주어진다.
다음 \(N\)개의 줄에는 각 목초지의 정보 \(x_i\), \(c_i\)가 주어진다. 이는 위치 \(x_i\)에 색 \(c_i\)를 가진 목초지가 존재한다는 뜻이다.
아름다운 별빛 목초지 삼중쌍의 개수를 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
서브태스크 1 | 5점 | \(N \le 300\) |
서브태스크 2 | 10점 | \(N \le 5000\) |
서브태스크 3 | 15점 | \(C = 3\) |
서브태스크 4 | 20점 | \(C \le 8\) |
서브태스크 5 | 20점 | 모든 위치 \(1, 2, \dots, L\)에 목초지가 존재한다. |
서브태스크 6 | 30점 | 추가 제한 없음 |
5 10 3
1 1
3 2
5 3
7 1
9 2
4
가능한 아름다운 별빛 목초지 삼중쌍은 다음과 같다.
| 위치 | 색 |
|---|---|
| 1, 3, 5 | 1, 2, 3 |
| 3, 5, 7 | 2, 3, 1 |
| 5, 7, 9 | 3, 1, 2 |
| 1, 5, 9 | 1, 3, 2 |
따라서 답은 \(4\)이다.
6 12 4
1 1
2 2
3 1
4 3
5 4
7 2
4
가능한 아름다운 별빛 목초지 삼중쌍은 다음과 같다.
| 위치 | 색 |
|---|---|
| 2, 3, 4 | 2, 1, 3 |
| 3, 4, 5 | 1, 3, 4 |
| 3, 5, 7 | 1, 4, 2 |
| 1, 4, 7 | 1, 3, 2 |
위치 \(3, 5, 7\) 역시 등차수열(\(x\) 간격 \(2\))이고 색 \(1, 4, 2\)가 모두 다르므로 조건을 만족한다.
따라서 답은 \(4\)이다.
4 8 3
1 1
3 1
5 2
7 3
1
위치 \(1, 3, 5\)는 등차수열이지만 색이 \(1, 1, 2\)이므로 세 색이 모두 다르지 않다.
위치 \(3, 5, 7\)은 등차수열이고 색이 \(1, 2, 3\)으로 모두 다르므로 조건을 만족한다.
따라서 답은 \(1\)이다.
해설
알파카컵 1회: J - 알파카의 별빛 목장
알파카컵 1회: J - 알파카의 별빛 목장
1. 문제 요약
\(1\)번부터 \(L\)번까지의 정수 좌표 위에 \(N\)개의 목초지가 있습니다. \(i\)번째 목초지는 서로 다른 위치 \(x_i\)에 있고 색 \(c_i\)를 가집니다(\(1 \le c_i \le C\), \(3 \le C \le 30\)).
다음 세 조건을 모두 만족하는 목초지 삼중쌍 \((a, b, c)\)의 개수를 구해야 합니다.
- 위치가 증가 순서: \(x_a < x_b < x_c\)
- 등차수열(가운데가 정확히 중앙): \(x_b - x_a = x_c - x_b\)
- 세 색이 모두 서로 다름: \(c_a, c_b, c_c\)가 모두 다름
핵심 관찰은 가운데 목초지 \(b\)를 기준으로 생각하는 것입니다. \(b\)의 위치를 \(m\), 공차를 \(d \ge 1\)이라 하면 양 끝 목초지는 정확히 위치 \(m-d\)와 \(m+d\)에 놓여야 합니다. 즉 모든 등차 삼중쌍은 (중점 \(m\), 거리 \(d\)) 한 쌍으로 유일하게 결정되며, 세 위치 \(m-d, m, m+d\)가 모두 목초지로 채워져 있어야 합니다. 색 조건만 없다면 이는 고전적인 자기 합성곱(self-convolution) 문제입니다.
2. [서브태스크 1]: \(N \le 300\)
\(N\)이 매우 작으므로 가장 단순한 완전 탐색이 통과합니다. 가운데 목초지 \(b\)를 고정하고, 다른 한 목초지를 왼쪽 끝 \(a\)로 두면 오른쪽 끝의 위치는 \(x_c = 2x_b - x_a\)로 결정됩니다. 그 위치에 목초지가 존재하는지 해시맵으로 확인한 뒤 세 색이 모두 다른지 검사하면 됩니다.
-
풀이: 모든 순서쌍 \((b, a)\)를 순회(\(x_a < x_b\))하며 \(x_c = 2x_b - x_a\)가 실제 목초지인지 조회합니다. 존재한다면 \(c_a, c_b, c_c\)가 모두 다른지 확인하여 답을 누적합니다. 각 삼중쌍은 가운데 \(b\)와 왼쪽 끝 \(a\)의 조합으로 유일하게 한 번 세어집니다.
-
시간 복잡도: 모든 \((b, a)\) 쌍을 보므로 \(O(N^2)\)입니다. \(N \le 300\)이면 약 \(9 \times 10^4\)번의 연산으로 충분히 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L, C;
ll x[200001], c[200001];
unordered_map<ll, ll> pos;
int main() {
fastio
cin >> n >> L >> C;
for (ll i = 1; i <= n; i++) {
cin >> x[i] >> c[i];
pos[x[i]] = c[i];
}
ll ans = 0;
for (ll b = 1; b <= n; b++) {
for (ll a = 1; a <= n; a++) {
if (x[a] >= x[b]) continue;
ll xc = m2(x[b]) - x[a];
auto it = pos.find(xc);
if (it == pos.end()) continue;
ll cc = it->second;
if (c[a] != c[b] && c[b] != cc && c[a] != cc) ans++;
}
}
cout << ans << endl;
return 0;
}
3. [서브태스크 2]: \(N \le 5000\)
서브태스크 1과 동일한 \(O(N^2)\) 완전 탐색이 그대로 통과하는 구간입니다. \(N \le 5000\)이면 최대 \(2.5 \times 10^7\)번의 연산으로, 해시맵 조회 상수가 다소 크더라도 제한 시간 내에 무리 없이 동작합니다.
-
풀이: 서브태스크 1과 같습니다. 다만 \(N\)이 커지므로
unordered_map의 충돌·재해싱 오버헤드를 줄이기 위해 위치를 미리 정렬한 뒤 이분 탐색으로 조회하거나, \(1 \le x_i \le L\)임을 이용해 길이 \(L+1\)짜리 배열로 색을 직접 인덱싱하면 상수가 크게 개선됩니다. 아래 코드는 위치 배열을 직접 사용하는 방식입니다. -
시간 복잡도: \(O(N^2)\)이며 위치 조회를 \(O(1)\) 배열 접근으로 처리합니다. 약 \(2.5 \times 10^7\)번의 연산으로 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L, C;
ll x[200001], c[200001];
ll color[200001]; // color[p] = 위치 p의 색 (없으면 0)
int main() {
fastio
cin >> n >> L >> C;
for (ll i = 1; i <= n; i++) {
cin >> x[i] >> c[i];
color[x[i]] = c[i];
}
ll ans = 0;
for (ll b = 1; b <= n; b++) {
for (ll a = 1; a <= n; a++) {
if (x[a] >= x[b]) continue;
ll xc = m2(x[b]) - x[a];
if (xc < 1 || xc > L) continue;
ll cc = color[xc];
if (cc == 0) continue; // 목초지 없음
if (c[a] != c[b] && c[b] != cc && c[a] != cc) ans++;
}
}
cout << ans << endl;
return 0;
}
4. [서브태스크 3]: \(C = 3\)
색이 정확히 3가지뿐이므로 세 색이 모두 다르다 \(\iff\) 세 색이 \(\{1, 2, 3\}\)의 한 배열이라는 강력한 동치가 성립합니다. 이 관찰은 포함-배제 없이도 곧장 합성곱으로 직결됩니다.
-
풀이: 가운데 목초지의 색을 \(c_b\)로 고정하면, 양 끝 목초지의 색은 나머지 두 색 \(\{p, q\} = \{1,2,3\} \setminus \{c_b\}\)여야 합니다. 색 \(t\)가 위치 \(p\)에 있으면 \(1\)인 지시 배열 \(\mathrm{occ}_t\)를 정의하고, 교차 합성곱 \(H_{p,q}[s] = \sum_{i+j=s} \mathrm{occ}_p[i]\,\mathrm{occ}_q[j]\)를 FFT로 계산합니다. 중점 \(m\), 거리 \(d\)인 삼중쌍의 두 끝 위치 합은 \((m-d)+(m+d) = 2m\)이므로, 중점 \(m\)에서 양 끝이 색 \(p, q\)인 삼중쌍의 수는 정확히 \(H_{p,q}[2m]\)입니다(\(p \ne q\)이므로 \(d = 0\) 항은 \(0\)이라 깔끔하게 처리됩니다). 색이 같은 두 위치를 따로 뺄 필요가 없어 단 몇 번의 합성곱이면 끝납니다.
-
시간 복잡도: 색깔별 지시 배열 3개에 대한 교차 합성곱 \(O(C^2)\)번을 각각 \(O(L \log L)\)에 수행하므로 \(O(C^2 L \log L)\)이지만, \(C = 3\)이므로 사실상 \(O(L \log L)\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using cd = complex<double>;
const double PI = acos(-1.0L);
void fft(vector<cd>& a, bool inv) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (inv ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int k = 0; k < len / 2; k++) {
cd u = a[i + k], v = a[i + k + len / 2] * w;
a[i + k] = u + v;
a[i + k + len / 2] = u - v;
w *= wlen;
}
}
}
if (inv) for (cd& z : a) z /= n;
}
vector<ll> cross(const vector<int>& A, const vector<int>& B) {
int n = 1;
while (n < (int)(A.size() + B.size())) n <<= 1;
vector<cd> fa(n), fb(n);
for (size_t i = 0; i < A.size(); i++) fa[i] = cd(A[i], 0);
for (size_t i = 0; i < B.size(); i++) fb[i] = cd(B[i], 0);
fft(fa, false); fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<ll> res(A.size() + B.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
ll n, L, C;
int col[200001];
int main() {
fastio
cin >> n >> L >> C;
int sz = L + 1;
vector<vector<int>> occ(4, vector<int>(sz, 0));
for (ll i = 0; i < n; i++) {
ll xx, cc; cin >> xx >> cc;
col[xx] = cc;
occ[cc][xx] = 1;
}
// H[p][q][s] = sum_{i+j=s} occ[p][i]*occ[q][j]
vector<vector<vector<ll>>> H(4, vector<vector<ll>>(4));
for (int p = 1; p <= 3; p++)
for (int q = 1; q <= 3; q++)
if (p != q) H[p][q] = cross(occ[p], occ[q]);
ll ans = 0;
for (ll m = 1; m <= L; m++) {
int cb = col[m];
if (!cb) continue;
int p = 0, q = 0;
for (int t = 1; t <= 3; t++) if (t != cb) { if (!p) p = t; else q = t; }
ans += H[p][q][m2(m)];
}
cout << ans << endl;
return 0;
}
5. [서브태스크 4]: \(C \le 8\)
색의 종류가 적지만 더 이상 "\(\{1,\dots,C\}\)의 배열"이라는 단순 동치는 쓸 수 없습니다. 대신 정해의 핵심인 포함-배제(inclusion–exclusion) 골격을 도입하되, 색의 수가 작으니 색별 자기 합성곱을 직접 모두 계산해도 충분합니다.
- 풀이: 색 조건을 무시한 전체 등차 삼중쌍 수에서, "세 색 중 어떤 두 색이 같은" 경우를 빼야 합니다. 세 색이 모두 다르다는 조건의 여사건은 다음 세 사건의 합집합입니다.
- \(E_1: c_a = c_b\), \(\quad E_2: c_b = c_c\), \(\quad E_3: c_a = c_c\)
이 셋 중 어느 둘이라도 동시에 성립하면 세 색이 모두 같아지므로, 임의의 두 사건의 교집합과 세 사건의 교집합은 모두 "세 색이 전부 같은" 사건 \(T\)와 일치합니다. 따라서 포함-배제에 의해
$$ (\text{모두 다름}) = (\text{전체}) - \big(|E_1| + |E_2| + |E_3|\big) + 2\,|T| $$
가 됩니다(자세한 유도는 6장 참고). 각 항은 색별 지시 배열 \(\mathrm{occ}_t\)의 자기/교차 합성곱으로 전부 계산할 수 있습니다. \(C \le 8\)이면 합성곱 횟수가 작으니 부담이 없습니다.
- 시간 복잡도: 전체 자기 합성곱 1회, 색별 자기 합성곱 \(C\)회, 색별 교차 합성곱 \(C\)회로 총 \(O(C \cdot L \log L)\)입니다. \(C \le 8\)에서 매우 여유롭습니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using cd = complex<double>;
const double PI = acos(-1.0L);
void fft(vector<cd>& a, bool inv) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (inv ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int k = 0; k < len / 2; k++) {
cd u = a[i + k], v = a[i + k + len / 2] * w;
a[i + k] = u + v;
a[i + k + len / 2] = u - v;
w *= wlen;
}
}
}
if (inv) for (cd& z : a) z /= n;
}
vector<ll> selfconv(const vector<int>& src) {
int n = 1;
while (n < 2 * (int)src.size()) n <<= 1;
vector<cd> fa(n);
for (size_t i = 0; i < src.size(); i++) fa[i] = cd(src[i], 0);
fft(fa, false);
for (int i = 0; i < n; i++) fa[i] *= fa[i];
fft(fa, true);
vector<ll> res(2 * src.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
vector<ll> cross(const vector<int>& A, const vector<int>& B) {
int n = 1;
while (n < (int)(A.size() + B.size())) n <<= 1;
vector<cd> fa(n), fb(n);
for (size_t i = 0; i < A.size(); i++) fa[i] = cd(A[i], 0);
for (size_t i = 0; i < B.size(); i++) fb[i] = cd(B[i], 0);
fft(fa, false); fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<ll> res(A.size() + B.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
ll n, L, C;
int col[200001];
int main() {
fastio
cin >> n >> L >> C;
int sz = L + 1;
vector<int> occ(sz, 0);
vector<vector<int>> occt(C + 1, vector<int>(sz, 0));
for (ll i = 0; i < n; i++) {
ll xx, cc; cin >> xx >> cc;
occ[xx] = 1; col[xx] = cc; occt[cc][xx] = 1;
}
vector<ll> g = selfconv(occ); // 전체 자기 합성곱
vector<vector<ll>> gt(C + 1), ht(C + 1);
for (ll t = 1; t <= C; t++) {
gt[t] = selfconv(occt[t]); // 색별 자기 합성곱
ht[t] = cross(occt[t], occ); // 색별 교차 합성곱
}
ll Total = 0, E3 = 0, E12 = 0, Tall = 0;
for (ll m = 1; m <= L; m++) {
if (!occ[m]) continue;
Total += d2(g[m2(m)] - 1); // (g[2m]-1)/2
ll s3 = 0;
for (ll t = 1; t <= C; t++) s3 += d2(gt[t][m2(m)] - occt[t][m]);
E3 += s3; // c_a=c_c
ll t = col[m];
E12 += ht[t][m2(m)] - 1; // c_a=c_b 와 c_b=c_c 합
Tall += d2(gt[t][m2(m)] - 1); // 세 색 모두 t
}
ll ans = Total - (E12 + E3) + m2(Tall);
cout << ans << endl;
return 0;
}
6. [서브태스크 5]: 모든 위치 \(1, 2, \dots, L\)에 목초지가 존재한다
모든 위치가 채워져 있으므로 지시 배열 \(\mathrm{occ}\)가 전부 \(1\)이 되어, 색을 무시한 전체 등차 삼중쌍 수는 합성곱 없이 닫힌 공식으로 즉시 구해집니다. 중점 \(m\)에서 가능한 거리 \(d\)는 \(1 \le d \le \min(m-1,\,L-m)\)이므로
$$ (\text{전체 등차 삼중쌍}) = \sum_{m=1}^{L} \min(m-1,\; L-m) $$
입니다. 이 경우 어려운 부분은 오직 색 조건뿐이며, 그 부분은 서브태스크 4·정해와 동일한 색별 합성곱 + 포함-배제로 처리하면 됩니다.
-
풀이: 전체 항만 위 닫힌 공식으로 \(O(L)\)에 대체하고, \(|E_1|, |E_2|, |E_3|, |T|\) 항은 색별 합성곱으로 계산합니다(아래 코드는 일반적인 정해와 동일한 합성곱 루틴을 쓰되, 모든 위치가 차 있다는 구조가 전체 항을 단순화함을 보여줍니다). 이 서브태스크는 "합성곱이 중점 합 \(2m\)에 대응된다"는 핵심 관찰을 검증하는 디딤돌 역할을 합니다.
-
시간 복잡도: 색별 합성곱이 지배하여 \(O(C \cdot L \log L)\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using cd = complex<double>;
const double PI = acos(-1.0L);
void fft(vector<cd>& a, bool inv) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (inv ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int k = 0; k < len / 2; k++) {
cd u = a[i + k], v = a[i + k + len / 2] * w;
a[i + k] = u + v;
a[i + k + len / 2] = u - v;
w *= wlen;
}
}
}
if (inv) for (cd& z : a) z /= n;
}
vector<ll> selfconv(const vector<int>& src) {
int n = 1;
while (n < 2 * (int)src.size()) n <<= 1;
vector<cd> fa(n);
for (size_t i = 0; i < src.size(); i++) fa[i] = cd(src[i], 0);
fft(fa, false);
for (int i = 0; i < n; i++) fa[i] *= fa[i];
fft(fa, true);
vector<ll> res(2 * src.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
vector<ll> cross(const vector<int>& A, const vector<int>& B) {
int n = 1;
while (n < (int)(A.size() + B.size())) n <<= 1;
vector<cd> fa(n), fb(n);
for (size_t i = 0; i < A.size(); i++) fa[i] = cd(A[i], 0);
for (size_t i = 0; i < B.size(); i++) fb[i] = cd(B[i], 0);
fft(fa, false); fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<ll> res(A.size() + B.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
ll n, L, C;
int col[200001];
int main() {
fastio
cin >> n >> L >> C;
int sz = L + 1;
vector<int> occ(sz, 0);
vector<vector<int>> occt(C + 1, vector<int>(sz, 0));
for (ll i = 0; i < n; i++) {
ll xx, cc; cin >> xx >> cc;
occ[xx] = 1; col[xx] = cc; occt[cc][xx] = 1;
}
// 모든 위치가 차 있다면 전체 항은 닫힌 공식으로 대체 가능:
// Total = sum_{m} min(m-1, L-m)
ll Total = 0;
for (ll m = 1; m <= L; m++) Total += min(m - 1, L - m);
vector<vector<ll>> gt(C + 1), ht(C + 1);
for (ll t = 1; t <= C; t++) {
gt[t] = selfconv(occt[t]);
ht[t] = cross(occt[t], occ);
}
ll E3 = 0, E12 = 0, Tall = 0;
for (ll m = 1; m <= L; m++) {
if (!occ[m]) continue;
ll s3 = 0;
for (ll t = 1; t <= C; t++) s3 += d2(gt[t][m2(m)] - occt[t][m]);
E3 += s3;
ll t = col[m];
E12 += ht[t][m2(m)] - 1;
Tall += d2(gt[t][m2(m)] - 1);
}
ll ans = Total - (E12 + E3) + m2(Tall);
cout << ans << endl;
return 0;
}
7. 정해
7.1 중점 기준 모델과 합성곱
가운데 목초지 \(b\)의 위치를 \(m\), 공차를 \(d \ge 1\)로 두면 양 끝 위치는 \(m-d\)와 \(m+d\)이고, 두 끝 위치의 합은 항상 \((m-d)+(m+d) = 2m\)으로 일정합니다. 위치 \(p\)가 목초지면 \(1\), 아니면 \(0\)인 지시 배열 \(\mathrm{occ}[p]\)를 정의하고 자기 합성곱
$$ g[s] = (\mathrm{occ} \star \mathrm{occ})[s] = \sum_{p+q=s} \mathrm{occ}[p]\,\mathrm{occ}[q] $$
을 생각합니다. \(g[2m]\)은 합이 \(2m\)인 모든 순서쌍 \((p, q)\)를 세며, 여기에는 \(p = q = m\)인 항(값 \(\mathrm{occ}[m]\)) 1개와, 서로 다른 두 위치 \(\{m-d, m+d\}\)를 두 가지 순서로 센 항들이 포함됩니다. 따라서 중점이 \(m\)인 (색 무시) 등차 삼중쌍의 수는
$$ \frac{g[2m] - \mathrm{occ}[m]}{2} $$
이고, \(m\) 자체가 목초지여야 하므로 색을 무시한 전체 삼중쌍 수는
$$ \text{Total} = \sum_{m=1}^{L} \mathrm{occ}[m]\cdot\frac{g[2m] - \mathrm{occ}[m]}{2}. $$
7.2 포함-배제로 "세 색 모두 다름" 세기
세 색이 모두 다르다는 조건의 여사건을 세 가지 색 일치 사건으로 나눕니다.
$$ E_1: c_a = c_b,\qquad E_2: c_b = c_c,\qquad E_3: c_a = c_c. $$
두 사건이 동시에 성립하면(예: \(E_1 \cap E_2 \Rightarrow c_a = c_b = c_c\)) 자동으로 세 색이 모두 같으므로,
$$ E_1 \cap E_2 = E_1 \cap E_3 = E_2 \cap E_3 = E_1 \cap E_2 \cap E_3 = T, $$
여기서 \(T\)는 "세 색이 모두 같은" 사건입니다. 포함-배제 공식
$$ |E_1 \cup E_2 \cup E_3| = \sum|E_i| - \sum|E_i \cap E_j| + |E_1 \cap E_2 \cap E_3| = (|E_1|+|E_2|+|E_3|) - 3|T| + |T| $$
이므로,
$$ (\text{모두 다름}) = \text{Total} - |E_1 \cup E_2 \cup E_3| = \text{Total} - (|E_1|+|E_2|+|E_3|) + 2|T|. $$
7.3 각 항을 합성곱으로 계산
색 \(t\)에 대한 지시 배열 \(\mathrm{occ}_t\)를 두고, \(g_t = \mathrm{occ}_t \star \mathrm{occ}_t\), \(h_t = \mathrm{occ}_t \star \mathrm{occ}\)로 정의합니다.
\(|E_3|\) (양 끝이 같은 색): 중점 \(m\)은 임의의 색, 양 끝이 같은 색 \(t\). 색 \(t\) 두 끝쌍의 수는 \(\tfrac{g_t[2m] - \mathrm{occ}_t[m]}{2}\)이고 가운데가 채워져 있어야 하므로
$$ |E_3| = \sum_{m:\ \mathrm{occ}[m]=1} \sum_{t=1}^{C} \frac{g_t[2m] - \mathrm{occ}_t[m]}{2}. $$
\(|E_1| + |E_2|\) (가운데가 한 끝과 같은 색): 가운데 \(m\)의 색은 \(t = c_m\)으로 고정됩니다. \(h_t[2m] = \sum_{p+q=2m}\mathrm{occ}_t[p]\,\mathrm{occ}[q]\)에서 \(p=q=m\)인 항(\(\mathrm{occ}_t[m]\,\mathrm{occ}[m] = 1\))을 빼면, 남는 항은 정확히 "한 끝이 색 \(t\), 반대 끝이 임의의 색"인 경우를 \(E_1\)(왼쪽 끝이 색 \(t\))과 \(E_2\)(오른쪽 끝이 색 \(t\)) 두 방향 모두 더한 값과 일치합니다(합성곱이 \(p
$$ |E_1| + |E_2| = \sum_{m:\ \mathrm{occ}[m]=1} \big(h_{c_m}[2m] - 1\big). $$
\(|T|\) (세 색 모두 같음): 색 \(t = c_m\)으로 세 위치 모두 색 \(t\). \(|T| = \sum_{m:\ \mathrm{occ}[m]=1} \tfrac{g_{c_m}[2m] - 1}{2}\).
최종적으로
$$ \boxed{\;(\text{답}) = \text{Total} - \big(|E_1|+|E_2|+|E_3|\big) + 2|T|\;} $$
을 출력합니다.
7.4 구현 및 정밀도
필요한 합성곱은 전체 자기 합성곱 1개, 색별 자기 합성곱 \(C\)개, 색별 교차 합성곱 \(C\)개로 총 \(2C+1\)개(\(\le 61\))입니다. 각 합성곱은 길이 약 \(2L\)의 FFT이므로 전체 시간 복잡도는 \(O(C \cdot L \log L)\)입니다.
값의 크기는 \(L \le 2\times10^5\), 합성곱 결과도 \(L\) 이하 수준이므로 double 기반 FFT의 누적 오차가 \(0.5\)보다 훨씬 작아 llround로 안전하게 반올림됩니다. 더 보수적으로 가려면 정수 정확도가 보장되는 NTT(예: \(998244353\) 모듈러; 결과가 \(64\)비트에 들어가므로 두 소수의 CRT 혹은 결과가 모듈러보다 작음을 이용)를 사용해도 됩니다. 답 자체는 최대 약 \(9 \times 10^9\) 규모로 long long에 들어갑니다.
- 시간 복잡도: \(O(C \cdot L \log L)\).
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using cd = complex<double>;
const double PI = acos(-1.0L);
void fft(vector<cd>& a, bool inv) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (inv ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int k = 0; k < len / 2; k++) {
cd u = a[i + k], v = a[i + k + len / 2] * w;
a[i + k] = u + v;
a[i + k + len / 2] = u - v;
w *= wlen;
}
}
}
if (inv) for (cd& z : a) z /= n;
}
vector<ll> selfconv(const vector<int>& src) {
int n = 1;
while (n < 2 * (int)src.size()) n <<= 1;
vector<cd> fa(n);
for (size_t i = 0; i < src.size(); i++) fa[i] = cd(src[i], 0);
fft(fa, false);
for (int i = 0; i < n; i++) fa[i] *= fa[i];
fft(fa, true);
vector<ll> res(2 * src.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
vector<ll> cross(const vector<int>& A, const vector<int>& B) {
int n = 1;
while (n < (int)(A.size() + B.size())) n <<= 1;
vector<cd> fa(n), fb(n);
for (size_t i = 0; i < A.size(); i++) fa[i] = cd(A[i], 0);
for (size_t i = 0; i < B.size(); i++) fb[i] = cd(B[i], 0);
fft(fa, false); fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<ll> res(A.size() + B.size() - 1);
for (size_t i = 0; i < res.size(); i++) res[i] = llround(fa[i].real());
return res;
}
ll n, L, C;
int col[200001];
int main() {
fastio
cin >> n >> L >> C;
int sz = L + 1;
vector<int> occ(sz, 0);
vector<vector<int>> occt(C + 1, vector<int>(sz, 0));
for (ll i = 0; i < n; i++) {
ll xx, cc; cin >> xx >> cc;
occ[xx] = 1; col[xx] = cc; occt[cc][xx] = 1;
}
vector<ll> g = selfconv(occ); // 전체 자기 합성곱
vector<vector<ll>> gt(C + 1), ht(C + 1);
for (ll t = 1; t <= C; t++) {
gt[t] = selfconv(occt[t]); // g_t
ht[t] = cross(occt[t], occ); // h_t
}
ll Total = 0, E3 = 0, E12 = 0, Tall = 0;
for (ll m = 1; m <= L; m++) {
if (!occ[m]) continue;
Total += d2(g[m2(m)] - 1); // (g[2m]-1)/2
ll s3 = 0;
for (ll t = 1; t <= C; t++) s3 += d2(gt[t][m2(m)] - occt[t][m]);
E3 += s3; // |E3|: 양 끝 동색
ll t = col[m];
E12 += ht[t][m2(m)] - 1; // |E1|+|E2|: 가운데가 한 끝과 동색
Tall += d2(gt[t][m2(m)] - 1); // |T|: 세 색 모두 동일
}
ll ans = Total - (E12 + E3) + m2(Tall); // 포함-배제
cout << ans << endl;
return 0;
}
평가 및 의견
알파카컵 1회: J - 알파카의 별빛 목장
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카컵 1회: J - 알파카의 별빛 목장