2개의 댓글이 있습니다.
-
-
restart -
전체 가짓수는 \(2^{n}-1\)입니다.(\(1 \le k\)이므로) 여기서 어떤 조합에 대해서 \(a_{i1}\)&\(a_{i2}\)&\(…a_{ik}\)의 값 \(p\)가 \(0\)이 아닌 가짓수를 뺍시다. \(U_{i}\)을 \(p\)의 \(i\)번째 비트가 켜져 있게끔 만드는 조합의 집합이라 한다면, 빼야 할 값은 \(|U_{0} \cup U_{1} \cup … \cup U_{20}|\)입니다. 그런데 \(f(x)\)의 정의에 따르면 \(2^{f(x)}-1\)는 \(p\)에서 \(x\)를 포함하게끔 만드는 조합의 가짓수가 되고, 편의상 아래서는 이 값을 \(f(x)\)로 부르면
\(|U_{0}|=f(1_{2})\)이고 \(|U_{1}|=f(10_{2})\)이고 \(|U_{2}|=f(100_{2})\).. 이런식으로 나갑니다. 또한 \(|U_{0} \cap U_{1}|=f(11_{2})\)이고 \(|U_{1} \cap U_{2}|=f(110_{2}) ... |U_{0} \cap U_{1} \cap U_{2}| = f(111_{2}) ...\) 뭐 이런식이 됩니다. \(g(x)\)만큼 교집합이 이루어지게 되는 거죠. 이제 포함배제 원리를 적용하면
\(|U_{0} \cup U_{1} \cup … \cup U_{20}|=\sum_{x=1}^{2^{20}} (-1)^{g(x)-1}(2^{f(x)}-1)\)이 되고 전체 가짓수와 빼면 해당 식이 나옵니다.
\(2^{f(x)}-1\)에서 뒷부분 \(-1\)은 다 모으면 \(_nC_0-_nC_1+_nC_2…_nC_n\)꼴로 그냥 없어집니다.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JAYS
위키 페이지에 나와있는 포함배제법칙을 이용한 문제를 풀어보다가 해결이 잘 안되어 글을 남깁니다.
현재 고민하고 있는 문제는 Codeforces에 있는 Jzzhu and Numbers 입니다. Editorial도 읽어보고 정답판정을 받은 코드도 읽어보았습니다만 어려움을 겪고 있습니다.
두 가지 부분에서 막히고 있는데 하나는 정답의 개수를 표현하는 최종수식(Editorial에 표현된 \(\sum(-1)^{g(x)}2^{f(x)}\))이고 다른 하나는 XOR 연산을 이용해 \(n*2^n\) Loop에서 계산하는 부분입니다. 이 두 가지 부분에 대한 도움을 구하고자 질문을 남깁니다.
위키페이지에 좋은 글 남겨주셔서 많이 배우고 있습니다. 항상 감사합니다.
11년 전