기본 조합 계수 문제

문제는 특정 조건을 만족하는 정점 집합의 개수를 세는 것으로, 주로 그래프 구조와 조합적 성질을 활용한다. 예를 들어, 트리에서 두 하위 트리의 크기가 k/2인 경우를 찾는 것은 이진 분할 기반의 조합 계산으로 해결 가능하다. 각 간선에 대해 양쪽 끝점이 모두 "좋은 점"일 확률을 계산하고, 이를 전체 가능한 선택지 중에서 비율로 표현하면 된다.

void dfs(int u, int parent) {
    s[u] = 1;
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == parent) continue;
        dfs(v, u);
        s[u] += s[v];
        ans += C(s[v], k / 2) * C(n - s[v], k / 2);
    }
}

경우의 수 동적 계획법 활용

두 부분 집합 A, B 사이의 방향성 조건을 만족하는 배치를 세는 문제에서는 상태 전이를 통해 모든 가능한 경로를 탐색한다. 새로운 정점을 A 또는 B에 추가할 때, 기존 집합 내부의 연결 관계에 따라 유효한 조합 수를 계산한다. 이 과정에서 이항 계수를 사용하여 선택 가능한 경우의 수를 정량화한다.

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k <= m; ++k) {
            for (int x = 0; x <= i; ++x)
                f[i+1][j][k+x] += C(i, x) * f[i][j][k];
            for (int x = 0; x <= j; ++x)
                f[i][j+1][k+i+x] += C(j, x) * f[i][j][k];
        }
    }

순서 기반 삽입 전략

특정 조건 아래에서 배열을 순차적으로 구성할 때, 거리 기준으로 원소를 정렬하고, 동일한 거리 내에서는 특정 범주 우선 삽입을 통해 불가능한 조합을 제거할 수 있다. 작은 값은 고정된 위치에 배치하고, 큰 값은 공백을 포함한 분할 방법(삽입 막대법)을 사용해 유동적인 배치를 구현한다.

sort(b + 1, b + idx + 1, [](const auto& a, const auto& b) {
    return abs(a.first * 2 - m) > abs(b.first * 2 - m) ||
           (abs(a.first * 2 - m) == abs(b.first * 2 - m) && a.first * 2 > m);
});

포함-배제 원리 및 소인수 처리

수의 소인수 조합을 기반으로 하는 문제에서는 대소 소수를 분류하고, 큰 소수에 대한 그룹화를 통해 조합 수를 효율적으로 계산한다. 작은 소수의 조합 상태를 기준으로 미리 계산된 테이블을 이용하며, 질문마다 해당 상태의 합계를 활용해 빠른 답변을 도출한다.

for (int s = now, pre = 1; pre; pre = (s - 1) & now, s = (s - 1) & now) {
    int val = 1, cnt = g[s];
    for (int p : primes) {
        int y = f[s][p];
        cnt -= y;
        val = val * (p2[y] - 1) % mod;
    }
    val = val * p2[cnt] % mod;
    if (popcnt[s] & 1) val = mod - val;
    ans = (ans + val) % mod;
}

격자 분할과 격자 검증

격자에서 특정 문자의 개수가 일정 조건을 만족하도록 분할하는 문제는 전처리된 누적합을 기반으로 판단된다. 가로/세로로 자르는 횟수를 시도하면서, 각 구역의 요소 수가 요구 조건에 맞는지 확인하고, 실제로 해당 구역이 유효한지 검사한다. 이후 가능한 분할 수를 곱해 최종 답을 구한다.

for (int i = 1; i <= c1; ++i)
    for (int j = 1; j <= c2; ++j)
        if (S(p1[i-1], p2[j-1], p1[i], p2[j]) != 2) return;

for (int i = 1; i < c1; ++i) res = res * cnt1[i] % mod;
for (int i = 1; i < c2; ++i) res = res * cnt2[i] % mod;
ans = (ans + res) % mod;

비트 연산 기반 구조 생성

비트 단위에서 상한을 넘지 않는 첫 번째 자리부터 조건을 만족하도록 조합을 생성하는 문제는, 각 비트 위치에서 가능한 값을 추적하는 다이나믹 프로그래밍으로 해결된다. 현재까지의 비트 합과, 한 번 이상 상한을 넘지 않은 숫자의 존재 여부를 상태로 저장해, 최종 결과를 누적한다.

for (int w = 31; w >= 0; --w) {
    if ((now ^ X) & (1 << w)) break;
    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int c = 0; c < 2; ++c)
            for (int x = 0; x < 2; ++x)
                if (f[i][c][x]) {
                    if (lim[i+1] & (1 << w)) {
                        add(f[i+1][c^1][x], f[i][c][x] * (lim[i+1] & U));
                        add(f[i+1][c][1], f[i][c][x] * (x ? (U+1) : 1));
                    } else {
                        add(f[i+1][c][x], f[i][c][x] * (lim[i+1] & U));
                    }
                }
    if (X & (1 << w)) add(ans, f[n][1][1]);
    else add(ans, f[n][0][1]);
}

구성 문제의 전략적 접근

게임판의 상태를 평행하게 만들기 위한 변환은 특정 패턴 기반의 분류로 이루어진다. 각 칸을 (x+y) mod 3 값에 따라 세 그룹으로 나누고, 각 그룹을 동일한 기호로 채워서 무승부 상태를 만든다. 가능한 변환 방법은 세 가지이며, 그 중 하나만 필요한 경우를 선택하면 최소 연산 횟수를 보장받는다.

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
        if (uid[i][j] == 0 && mp[i][j] == 'O') ans1[i][j] = 'X';
        if (uid[i][j] == 1 && mp[i][j] == 'X') ans1[i][j] = 'O';
    }

그래프 기반 순환 탐색

각 인덱스가 i - a_i로 연결되는 방향 그래프에서, 각 노드의 출도가 1이므로 사이클이 존재할 수밖에 없다. 사이클 내부의 모든 정점은 원래 조건을 만족하며, 합이 0이 되는 것이 증명되며, 이는 원래 배열의 조건을 만족하는 해임을 의미한다. 따라서 사이클을 탐색하여 결과를 출력하면 된다.

while (!vis[x]) {
    vis[x] = 1;
    x = a[x];
}
ans.push_back(x);
while (x != ans[0]) {
    ans.push_back(x);
    x = a[x];
}

요리 조합 최적화

제품 조합 문제는 각 재료의 조합 조건을 기반으로 가능한 조합을 찾는 문제이다. 여러 조건을 동시에 만족하는 조합을 찾기 위해, 조건을 분해하고, 각 조건에 대해 가능한 조합 수를 계산한 후, 이를 결합하여 전체 조합 수를 산출한다.