2803번: KOŠARE

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

$O(m(n+2^m))$

풀이:
http://hsin.hr/coci/archive/2011_2012/contest6_solutions.zip
6번 참조

#include<cstdio>
#define mod int(1e9+7)
int n, m, r;
long long c[1 << 20];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1 << m; i--;) c[i]++;
    while (n--) {
        int k, x, tot = 0;
        for (scanf("%d", &k); k--;) {
            scanf("%d", &x);
            tot += 1 << x - 1;
        }
        c[tot] = c[tot] * 2 % mod;
    }
    for (int i = 1; i < 1 << m; i *= 2)
        for (int j = 1 << m; j--;) if (i&j) c[j] = c[j] * c[j^i] % mod;
    for (int i = 1 << m; i--;) {
        int b = 0;
        for (int j = i; j; j &= j - 1) b++;
        r = (r + mod + c[i] * (m - b & 1 ? -1 : 1)) % mod;
    }
    printf("%d", r);
    return 0;
}

2893번: XOR 도형

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

$O(2^n)$

x=a, y=b, x+y=c 로 이루어진 직각이등변삼각형을 (a,b,c)로 표현하자.

주어진 삼각형을 이루는 점들 집합을 ti라 하자.
구하고자 하는 구역
r=
sum(ti)
-2*sum(ti∩tj)
+4*sum(ti∩tj∩tk)
...

r구하기 위해 ti들을 교집합하는 연산을 구현해야 한다.
ti(ai,bi,ci)라고 하자.
ti∩tj를 잘 생각해보면 max(ai,aj)+max(bi,bj)<min(ci,cj) 인 경우 (max(ai,aj),max(bi,bj),min(ci,cj)) 인 직각이등변 삼각형이 됨을 알 수 있다.(위 부등식을 만족하지 않으면 ∅이다.)

∅이 아닌 경우만 따져서 계산하여 r을 구해주면 된다.

#include<cstdio>
int n, x[10], y[10], z[10];
double s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", x + i, y + i, z + i), z[i] += x[i] + y[i];
    for (int i = 1; i < 1 << n; i++) {
        int m = 1, a = 0, b = 0, c = 1e9;
        for (int j = 0; j<n; j++) if (i&(1 << j)) {
            m *= -2;
            if (a<x[j]) a = x[j];
            if (b<y[j]) b = y[j];
            if (c>z[j]) c = z[j];
        }
        s += (a + b < c) / -4.0*(c - a - b)*(c - a - b)*m;
    }
    printf("%.1lf", s);
    return 0;
}