문제 1: 동적 문자열 집합에서 고유 문자열 수 계산

여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다.

해결 핵심은 다음과 같다:

• 각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다.
• 해시 함수는 다항식 해시를 기반으로 하며, 베이스 값 \( B \)를 이용해 위치별 가중치를 부여한다.
• 모든 문자열의 현재 해시값을 관리하는 자료구조로 std::map 기반의 카운터를 사용하여 중복 제거된 개수를 유지한다.

핵심 구현 로직

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const int MAX_LEN = 5e5 + 10;
const int BASE = 3331;

ull power[MAX_LEN], prefixSum[MAX_LEN];

struct LazySegmentTree {
    vector<ull> hashVal;
    vector<int> lazy, leftBound, rightBound;
    int size;

    LazySegmentTree(int n) : size(n) {
        int nodes = (n + 5) << 2;
        hashVal.resize(nodes);
        lazy.assign(nodes, 0);
        leftBound.resize(nodes);
        rightBound.resize(nodes);
    }

    void merge(int u) {
        hashVal[u] = hashVal[u << 1] + hashVal[u << 1 | 1];
    }

    void propagate(int u) {
        if (lazy[u]) {
            int l = leftBound[u], r = rightBound[u];
            hashVal[u] = (prefixSum[r] - prefixSum[l-1]) * lazy[u];
            if (l != r) {
                lazy[u << 1] = lazy[u];
                lazy[u << 1 | 1] = lazy[u];
            }
            lazy[u] = 0;
        }
    }

    void build(int u, int l, int r, const vector<int>& arr) {
        leftBound[u] = l; rightBound[u] = r;
        if (l == r) {
            hashVal[u] = arr[l] * power[l];
            return;
        }
        int mid = (l + r) / 2;
        build(u << 1, l, mid, arr);
        build(u << 1 | 1, mid+1, r, arr);
        merge(u);
    }

    void updateRange(int u, int l, int r, int val) {
        propagate(u);
        if (r < leftBound[u] || rightBound[u] < l) return;
        if (l <= leftBound[u] && rightBound[u] <= r) {
            lazy[u] = val;
            propagate(u);
            return;
        }
        updateRange(u << 1, l, r, val);
        updateRange(u << 1 | 1, l, r, val);
        propagate(u << 1); propagate(u << 1 | 1);
        merge(u);
    }

    ull queryHash(int u, int l, int r) {
        propagate(u);
        if (l <= leftBound[u] && rightBound[u] <= r) {
            return hashVal[u];
        }
        ull result = 0;
        if (l <= (leftBound[u] + rightBound[u]) / 2)
            result += queryHash(u << 1, l, r);
        else
            result += queryHash(u << 1 | 1, l, r);
        return result;
    }
};

struct UniqueCounter {
    map<ull, int> countMap;
    int distinctCount;

    UniqueCounter() : distinctCount(0) {}

    void add(ull h) {
        if (countMap[h] == 0) distinctCount++;
        countMap[h]++;
    }

    void remove(ull h) {
        countMap[h]--;
        if (countMap[h] == 0) distinctCount--;
    }

    int size() const { return distinctCount; }
};

void solveStringProblem() {
    int n, len, m;
    cin >> n >> len >> m;

    power[0] = 1;
    for (int i = 1; i <= len; ++i)
        power[i] = power[i-1] * BASE;
    for (int i = 1; i <= len; ++i)
        prefixSum[i] = prefixSum[i-1] + power[i];

    vector<LazySegmentTree> trees;
    UniqueCounter counter;

    for (int i = 0; i < n; ++i) {
        trees.emplace_back(len);
        string s;
        cin >> s;
        vector<int> arr(len + 1);
        for (int j = 0; j < len; ++j)
            arr[j+1] = s[j] - 'a' + 1;
        trees[i].build(1, 1, len, arr);
        counter.add(trees[i].queryHash(1, 1, len));
    }

    while (m--) {
        int x, l, r; char c;
        cin >> x >> l >> r >> c;
        --x;
        ull oldHash = trees[x].queryHash(1, 1, len);
        counter.remove(oldHash);
        trees[x].updateRange(1, l, r, c - 'a' + 1);
        ull newHash = trees[x].queryHash(1, 1, len);
        counter.add(newHash);
        cout << counter.size() << '\n';
    }
}

문제 2: 서브트리 내 정점 순회 시 북쪽 이동 횟수 조건 만족 경우의 수

루트가 1인 트리에서, 각 쿼리는 특정 노드의 서브트리에 대해, 모든 정점을 한 번씩 방문하면서 정확히 \( y \)번 조상(북쪽) 방향으로 이동하는 경로의 수를 묻는다.

이 문제는 다음 아이디어로 해결:

• \( f[u][k] \): 정점 \( u \) 의 서브트리에서, 적어도 \( k \)번 북쪽 이동을 포함하는 순회 방법의 수 (이후 포함-배제 원리 적용).
• 서브트리 병합 시, 두 서브트리의 크기와 이동 횟수를 결합할 때 이항 계수를 사용해 가능한 삽입 위치를 계산한다.
• 최종 결과는 포함-배제를 통해 "정확히 \( y \)"번 이동하는 경우를 추출한다.

핵심 점화식

\[ g[k] = \sum_{i+j=k} f[\text{parent}][i] \cdot f[\text{child}][j] \cdot \binom{(s_p - i) + (s_c - j)}{s_p - i} \] 여기서 \( s_p, s_c \)는 각각 부모/자식 서브트리의 크기이다.

const int MAX_N = 5005;
const int MOD = 1e9 + 7;

int C[MAX_N][MAX_N];
vector<int> graph[MAX_N];
long long dp[MAX_N][MAX_N], temp[MAX_N];
int subtreeSize[MAX_N];

void precomputeComb() {
    for (int i = 0; i < MAX_N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}

void dfs(int u, int parent) {
    dp[u][0] = 1;
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);
        memset(temp, 0, sizeof(temp));
        for (int i = 0; i <= subtreeSize[u]; ++i) {
            for (int j = 0; j < subtreeSize[v]; ++j) {
                long long ways = (dp[u][i] * dp[v][j]) % MOD;
                ways = (ways * C[subtreeSize[u] - i + subtreeSize[v] - j][subtreeSize[u] - i]) % MOD;
                temp[i + j] = (temp[i + j] + ways) % MOD;
            }
        }
        subtreeSize[u] += subtreeSize[v];
        for (int i = 0; i <= subtreeSize[u]; ++i)
            dp[u][i] = temp[i];
    }
    // Update with current node addition
    for (int i = subtreeSize[u]; i >= 0; --i) {
        long long val = dp[u][i];
        if (i) val = (val + dp[u][i-1]) % MOD;
        val = (val * (subtreeSize[u] + 1 - i)) % MOD;
        dp[u][i] = val;
    }
    subtreeSize[u]++;
}

void solveTreeProblem() {
    int n, q;
    cin >> n >> q;
    precomputeComb();
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        long long res = 0;
        for (int j = y; j <= subtreeSize[x]; ++j) {
            long long term = (dp[x][j] * C[j][y]) % MOD;
            if ((j - y) % 2) res = (res - term + MOD) % MOD;
            else res = (res + term) % MOD;
        }
        cout << res << '\n';
    }
}

문제 3: 01 행렬 내 정사각형 꼭짓점 조합 계산

\( N \times N \) 크기의 이진 행렬에서, 값이 1인 네 점이 정사각형의 네 꼭짓점을 이루는 조합의 수를 구하라. 단, 회전 및 대칭은 고려하지 않는다.

직접적인 \( O(N^4) \) 접근은 비효율적이므로 다음과 같은 최적화를 사용:

• bitset을 사용해 행 단위의 비트 연산을 수행함으로써 상수 시간 내 교집합 연산을 가능하게 한다.
• 두 점 \((i,j)\), \((i,j+d)\)를 한 변으로 하는 정사각형을 기준으로, 나머지 두 점 \((i+d,j)\), \((i+d,j+d)\)가 존재하는지를 확인한다.
• 또한 대각선 방향에 대한 경우도 고려하여 모든 가능한 정사각형을 포괄한다.

비트셋 기반 알고리즘

const int MAX = 501;
bitset<MAX> grid[MAX], shifted[MAX];

void solveSquareProblem() {
    int n, type;
    cin >> n >> type;
    if (type == 5) {
        cout << "0\n";
        return;
    }

    for (int i = 1; i <= n; ++i) {
        string row;
        cin >> row;
        for (int j = 1; j <= n; ++j)
            if (row[j-1] == '1')
                grid[i][j] = 1;
    }

    long long total = 0;

    // Case 1: Axis-aligned squares
    for (int d = 1; d < n; ++d) {
        for (int i = 1; i <= n; ++i)
            shifted[i] = grid[i] >> d;

        for (int i = 1; i <= n - d; ++i) {
            for (int j = 1; j <= n - d; ++j) {
                if (grid[i][j] && shifted[i][j] && grid[i+d][j] && shifted[i+d][j])
                    total++;
            }
        }
    }

    // Case 2: Rotated squares using bitset intersection
    for (int dx = 1; dx < n; ++dx) {
        for (int dy = 1; dy < n; ++dy) {
            if (dx*dx + dy*dy == 0) continue;
            for (int i = 1; i <= n; ++i)
                shifted[i] = (grid[i] >> dx);

            for (int i = 1; i <= n - dy; ++i) {
                for (int j = 1; j <= n - dx; ++j) {
                    bitset<MAX> candidate = grid[i][j] & shifted[i][j] & grid[i+dy][j+dx] & shifted[i+dy][j+dx];
                    total += candidate.count();
                }
            }
        }
    }

    cout << total << '\n';
}