[백준] 30806. 교차 집합 크기 합

https://www.acmicpc.net/problem/30806

문제 요약

• 집합들이 주어짐 : 원소(1 ~ 10^9), 집합 원소 개수의 합(10^6)
• 모든 교집합 들이 있을 때 교집합 크기별 원소 개수들의 합

접근법

• 교집합을 다 구하는 것은 현실적으로 불가능함
• 어떤 원소가 어디에 포함되어있을까? -> count가 가능함
  • 1이 총 10번 등장했다면
  • 1은 크기 1 ~ 10인 교집합의 개수에 영향을 주었을 것임
  • 크기 1 : 10개에 영향
  • 크기 2 : 크기 2의 가능한 경우의 수? ${_{10}C_{2}}$ 개에 영향
  • 크기 3 : 크기 3의 가능한 경우의 수? ${_{10}C_{3}}$ 개에 영향
• 그런데 실행 시간은?
  • 조합을 구하는데 factorial만큼 계산을 하고
  • 각각의 경우에 대해서 1 부터 k까지 계산을 하고
  • 원소의 개수가 n개라면?
• 조합
  • factorial을 미리 구해놓고
  • ${_nC_r = \frac {n!}{(n-r)!r!}}$ 을 구하면 되는데
  • modular 역원을 이용함
• 각각의 경우에 대해 1부터 k
  • 이 부분에서 생각의 전환이 힘들었음(editorial을 보고 용기를 얻음)
  • 각각의 경우에 대해 1~k이긴 하지만 모두 합쳐 놓고 보면 전체 개수인 n을 넘지 않을 것임
  • 즉 1이 5000개, 2가 100000개, 3이 9999999개, ... 있다고 해도
  • 모두 합하면 n을 넘지 않기 때문에 계산해야하는 양도 n 임!!

참고

• https://solved.ac/arena/15/editorial