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*2n$ Loop에서 계산하는 부분입니다. 이 두 가지 부분에 대한 도움을 구하고자 질문을 남깁니다.
위키페이지에 좋은 글 남겨주셔서 많이 배우고 있습니다. 항상 감사합니다.
11년 전