집합에 들어가는 모든 원소를 map에 {s, 등장횟수} 로 저장함, 이렇게 하면 수 s가 몇 개의 집합에서 등장했는지 알 수 있음.

k개 집합의 교집합에 s가 있으려면 k개 집합이 모두 s를 포함해야 함. 이를 만족시키는 경우의 수는 comb(k, s) 이므로, s는 comb(k, s) 개의 집합에 등장함

이를 집합의 모든 수 s에 대해 반복해주면 k개 집합의 교집합들에 각 수가 몇 번씩 들어가는지 알 수 있음. 즉 map의 순서쌍 {s, freq(s)}에 대해 comb(k, freq(s))의 합이 k개 집합의 교집합의 크기 총합이 됨

시간복잡도는 O(n log n) 인거같다. 엄밀한 증명은 몰?루

- dc official App