[NOI2025 예선 R1] A - 기본 사이클 구조

다음의 수학적 원리를 활용한다:

Cayley 정리
n개의 노드가 k개의 연결 성분으로 구성되어 있을 때, 이들을 연결하기 위해 k-1개의 간선을 추가하는 방법의 수는 n^(k−2) × ∏(i=1 to k) size_i이다.

이 정리를 바탕으로, 입력 그래프에 이미 사이클이 존재하는 경우 답을 직접 계산할 수 있다.

반면, 초기 상태에서 사이클이 없는 경우, 가능한 사이클 조합을 모두 탐색해야 한다.

각 연결 성분의 크기만 기억한 후, 일부 성분들을 선택하여 사이클을 형성하는 경우를 고려하자.

• c = 1인 경우: 해당 성분 내부에 간선 하나를 추가하면 된다. 가능한 방법은 sz*(sz-1)/2 - sz + 1.
• c = 2인 경우: 두 성분 각각에서 한 개씩 간선을 추가하여 연결. 가능한 경우의 수는 (sz₁*sz₂)*(sz₁*sz₂ - 1)/2.
• c ≥ 3인 경우: 순환 구조를 만들기 위해 (c-1)!/2 가지 회전 및 반전 대칭을 고려하고, 인접한 성분 간 연결 수를 곱해준다.

DP를 통해 c, ∑size를 상태로 하고 ∏size를 값으로 관리하면 시간 복잡도 O(n²)까지 최적화 가능하다.

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

int mod_add(int a, int b) { return (a + b) % MOD; }
int mod_sub(int a, int b) { return (a - b + MOD) % MOD; }
int mod_mul(long long a, long long b) { return (a * b) % MOD; }

int power(int base, int exp) {
    int result = 1;
    while(exp) {
        if(exp & 1) result = mod_mul(result, base);
        base = mod_mul(base, base);
        exp >>= 1;
    }
    return result;
}

int n, m;
int parent[MAXN], sz[MAXN];

int root(int x) {
    return parent[x] == x ? x : parent[x] = root(parent[x]);
}

void unite(int a, int b) {
    a = root(a), b = root(b);
    if(a != b) {
        sz[a] += sz[b];
        parent[b] = a;
    }
}

int fact[MAXN], inv_fact[MAXN], powers[MAXN];
int component_sizes[MAXN], total_components;

void preprocess() {
    fact[0] = 1;
    for(int i = 1; i <= n; ++i)
        fact[i] = mod_mul(fact[i - 1], i);

    inv_fact[n] = power(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; --i)
        inv_fact[i] = mod_mul(inv_fact[i + 1], i + 1);

    powers[0] = 1;
    for(int i = 1; i <= n; ++i)
        powers[i] = mod_mul(powers[i - 1], n);
}

int comb2(int x) {
    return mod_mul(mod_mul(x, x - 1), inv_fact[2]);
}

int dp_table[MAXN][2];

void compute() {
    cin >> n >> m;

    for(int i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }

    bool has_cycle = false;
    for(int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if(root(u) == root(v))
            has_cycle = true;
        else
            unite(u, v);
    }

    preprocess();

    if(has_cycle) {
        int components = 0, product = 1;
        for(int i = 1; i <= n; ++i) {
            if(root(i) == i) {
                components++;
                product = mod_mul(product, sz[i]);
            }
        }
        int answer = mod_mul(product, powers[components - 2]);
        cout << answer << "\n";
        return;
    }

    vector<int> sizes;
    for(int i = 1; i <= n; ++i) {
        if(root(i) == i)
            sizes.push_back(sz[i]);
    }

    sort(sizes.begin(), sizes.end());
    int total_size_product = 1;
    for(auto s : sizes)
        total_size_product = mod_mul(total_size_product, s);

    int answer = 0;

    // c = 1
    for(auto s : sizes) {
        if(s > 2) {
            int ways = mod_sub(comb2(s), s - 1);
            answer = mod_add(answer, mod_mul(ways, mod_mul(total_size_product, powers[sizes.size() - 2])));
        }
    }

    // c = 2
    if(sizes.size() == 2) {
        int prod = mod_mul(sizes[0], sizes[1]);
        answer = mod_add(answer, comb2(prod));
    }

    // c >= 3
    if(sizes.size() >= 3) {
        memset(dp_table, 0, sizeof dp_table);
        dp_table[0][0] = 1;

        for(int i = 0; i < sizes.size(); ++i) {
            for(int j = i + 1; j >= 1; --j) {
                dp_table[j][0] = mod_add(dp_table[j][0], mod_mul(dp_table[j - 1][0], sizes[i]));
                dp_table[j][1] = mod_add(dp_table[j][1], mod_add(
                    mod_mul(dp_table[j - 1][1], sizes[i]),
                    mod_mul(dp_table[j - 1][0], mod_mul(sizes[i], sizes[i]))
                ));
            }
        }

        for(int c = 3; c <= sizes.size(); ++c) {
            int term = mod_mul(dp_table[c][1], mod_mul(powers[sizes.size() - c - 1], total_size_product));
            term = mod_mul(term, mod_mul(fact[c - 1], (MOD + 1) / 2));
            answer = mod_add(answer, term);
        }
    }

    cout << answer << "\n";
}

[NOI2025 예선 R1] B - 작업 롤백

세그먼트 트리를 사용하여 실시간으로 쿼리에 응답하면서도 과거 상태로 되돌릴 수 있는 구조를 설계한다.

const int MAXQ = 300005;
int n, q;
vector<array<int, 3>> updates[MAXQ];
vector<int> queries[MAXQ];
long long answers[MAXQ];

struct SegmentNode {
    int left_len, right_len;
    long long value;
};

class PersistentSegmentTree {
private:
    int left_idx[4 * MAXQ], right_idx[4 * MAXQ];
    SegmentNode tree[4 * MAXQ];
    int node_count = 0;

    long long query_internal(int node, int k) {
        if(k <= 0) return tree[node].value;
        if(k >= tree[node].right_len) return 0;
        int lc = node * 2, rc = node * 2 + 1;
        if(k <= tree[rc].right_len)
            return tree[node].value - tree[rc].value + query_internal(rc, k);
        else
            return query_internal(lc, k - tree[rc].right_len + tree[rc].left_len);
    }

    SegmentNode merge_nodes(int l_node, SegmentNode r_node) {
        if(tree[l_node].right_len <= r_node.left_len) {
            return {tree[l_node].left_len + r_node.left_len - tree[l_node].right_len, r_node.right_len, r_node.value};
        } else {
            long long merged_value = query_internal(l_node, r_node.left_len) + r_node.value;
            return {tree[l_node].left_len, tree[l_node].right_len - r_node.left_len + r_node.right_len, merged_value};
        }
    }

public:
    void build(int node, int l, int r) {
        left_idx[node] = l;
        right_idx[node] = r;
        if(l == r) return;
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
    }

    void update(int node, int pos, int type, int val) {
        if(left_idx[node] == right_idx[node]) {
            if(type == 0) tree[node] = {0, 0, 0};
            if(type == 1) tree[node] = {0, 1, val};
            if(type == 2) tree[node] = {1, 0, 0};
            return;
        }
        int mid = (left_idx[node] + right_idx[node]) / 2;
        if(pos <= mid)
            update(node * 2, pos, type, val);
        else
            update(node * 2 + 1, pos, type, val);
        tree[node] = merge_nodes(node * 2, tree[node * 2 + 1]);
    }

    SegmentNode query_range(int node, int end_pos) {
        if(right_idx[node] <= end_pos) return tree[node];
        int mid = (left_idx[node] + right_idx[node]) / 2;
        if(end_pos <= mid) return query_range(node * 2, end_pos);
        return merge_nodes(node * 2, query_range(node * 2 + 1, end_pos));
    }
} seg_tree;

void process_queries() {
    cin >> n >> q;

    for(int i = 1; i <= q; ++i) {
        int op; cin >> op;
        if(op == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            updates[l].push_back({i, 1, x});
            updates[r + 1].push_back({i, 0, 0});
        } else if(op == 2) {
            int l, r;
            cin >> l >> r;
            updates[l].push_back({i, 2, 0});
            updates[r + 1].push_back({i, 0, 0});
        } else {
            int idx; cin >> idx;
            queries[idx].push_back(i);
        }
    }

    fill(answers, answers + MAXQ, -1);
    seg_tree.build(1, 1, q);

    for(int i = 1; i <= n; ++i) {
        for(auto& upd : updates[i])
            seg_tree.update(1, upd[0], upd[1], upd[2]);

        for(int query_time : queries[i]) {
            auto res = seg_tree.query_range(1, query_time);
            answers[query_time] = res.value;
        }
    }

    for(int i = 1; i <= q; ++i)
        if(answers[i] != -1)
            cout << answers[i] << "\n";
}

[NOI2025 예선 R2] A - 강수량 분석

특정 수열의 합과 팩토리얼 값을 기반으로 결과를 도출하는 문제이다.

const int LIMIT = 200000;
const int PRIME = 998244353;

int mod_add(int a, int b) { return (a + b) % PRIME; }
int mod_sub(int a, int b) { return (a - b + PRIME) % PRIME; }
int mod_mul(long long a, long long b) { return (a * b) % PRIME; }

int factorial[LIMIT + 5];
long long prefix_sums[LIMIT + 5];
int cumulative_factorial[LIMIT + 5];

void initialize(int limit) {
    factorial[0] = 1;
    for(int i = 1; i <= limit; ++i)
        factorial[i] = mod_mul(factorial[i - 1], i);

    for(int i = 1; i <= limit; ++i)
        prefix_sums[i] = prefix_sums[i - 1] + 1LL * i * i;

    for(int i = 1; i <= limit; ++i)
        cumulative_factorial[i] = mod_add(cumulative_factorial[i - 1], mod_mul(i, factorial[i]));
}

long long ceil_div(long long a, long long b) {
    return (a + b - 1) / b;
}

void calculate_rainfall() {
    long long target; cin >> target;
    target++;

    int low = 1, high = LIMIT, position = 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(prefix_sums[mid] >= target) {
            position = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    int result = 0;
    long long quotient = ceil_div(target - prefix_sums[position - 1], position);
    target -= quotient * position;
    result = mod_add(result, mod_mul(quotient, factorial[position]));

    position--;
    if(target == prefix_sums[position]) {
        result = mod_add(result, cumulative_factorial[position]);
    } else {
        int diff = prefix_sums[position] - target;
        result = mod_add(result, cumulative_factorial[position]);
        result = mod_sub(result, factorial[diff]);
    }

    cout << result << "\n";
}

[NOI2025 예선 R2] B - 모래 폭풍 시뮬레이션

다이나믹 프로그래밍과 다익스트라 알고리즘을 결합하여 최단 경로를 구하는 문제이다.

const int NODE_LIMIT = 505;
int iterations, node_count, cost_coefficient;
int heights[NODE_LIMIT], delays[NODE_LIMIT];
long long weights[NODE_LIMIT][NODE_LIMIT];
long long distances[NODE_LIMIT][NODE_LIMIT];
long long start_distances[NODE_LIMIT][NODE_LIMIT];
long long end_distances[NODE_LIMIT][NODE_LIMIT];
long long final_result[NODE_LIMIT][NODE_LIMIT];

bool visited[NODE_LIMIT];

void simulate_sandstorm() {
    cin >> iterations >> node_count >> cost_coefficient;

    for(int i = 1; i <= node_count; ++i)
        cin >> heights[i];

    for(int i = 1; i <= node_count; ++i)
        cin >> delays[i];

    for(int i = 1; i <= node_count; ++i)
        for(int j = 1; j <= node_count; ++j)
            cin >> weights[i][j];

    const long long INF = 1LL << 60;
    for(int i = 1; i <= node_count; ++i)
        for(int j = 1; j <= node_count; ++j)
            final_result[i][j] = INF;

    for(int i = 1; i <= node_count; ++i) {
        for(int j = 1; j <= node_count; ++j) {
            long long edge_weight = weights[i][j] + 1LL * abs(heights[i] - heights[j]) * cost_coefficient;
            distances[i][j] = start_distances[i][j] = end_distances[i][j] = edge_weight;
        }
    }

    for(int source = 1; source <= node_count; ++source) {
        vector<long long> dist(node_count + 1, INF);
        fill(visited, visited + NODE_LIMIT, false);
        dist[source] = 0;

        while(true) {
            int current = -1;
            for(int i = 1; i <= node_count; ++i) {
                if(!visited[i] && (current == -1 || dist[current] > dist[i]))
                    current = i;
            }
            if(current == -1) break;
            visited[current] = true;

            for(int next = 1; next <= node_count; ++next) {
                long long weight = weights[current][next] + 1LL * abs(heights[source] - heights[next]) * delays[next];
                if(dist[next] > dist[current] + weight)
                    dist[next] = dist[current] + weight;
            }
        }

        for(int i = 1; i <= node_count; ++i) {
            distances[source][i] = dist[i];
            start_distances[i][source] = min(start_distances[i][source], dist[i]);
            end_distances[source][i] = min(end_distances[source][i], dist[i]);
        }
    }

    for(int l = 1; l <= node_count; ++l) {
        for(int r = 1; r <= node_count; ++r) {
            for(int mid = 1; mid <= node_count; ++mid) {
                long long combined_cost = distances[l][mid] + distances[r][mid];
                long long left_penalty = 1LL * abs(heights[mid] - heights[l]) * delays[mid];
                long long right_penalty = 1LL * abs(heights[mid] - heights[r]) * delays[mid];
                combined_cost -= max(left_penalty, right_penalty);
                combined_cost += 1LL * abs(heights[l] - heights[r]) * cost_coefficient;
                distances[l][r] = min(distances[l][r], combined_cost);
            }
        }
    }

    for(int k = 1; k <= node_count; ++k)
        for(int i = 1; i <= node_count; ++i)
            for(int j = 1; j <= node_count; ++j)
                distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j]);

    for(int k = 1; k <= node_count; ++k)
        for(int i = 1; i <= node_count; ++i)
            for(int j = 1; j <= node_count; ++j)
                start_distances[i][j] = min(start_distances[i][j], start_distances[i][k] + distances[k][j]);

    for(int k = 1; k <= node_count; ++k)
        for(int i = 1; i <= node_count; ++i)
            for(int j = 1; j <= node_count; ++j)
                final_result[i][j] = min(final_result[i][j], start_distances[i][k] + end_distances[k][j]);

    for(int i = 1; i <= node_count; ++i) {
        for(int j = 1; j <= node_count; ++j)
            cout << final_result[i][j] << " ";
        cout << "\n";
    }
}

[NOI2025 예선 R2] C - 우주 방사선

소수와 조합론을 기반으로 한 수학적 계산 문제이다.

const int MAX_NUM = 25000005;
const int MOD = 998244353;

int mod_add(int a, int b) { return (a + b) % MOD; }
int mod_sub(int a, int b) { return (a - b + MOD) % MOD; }
int mod_mul(long long a, long long b) { return (a * b) % MOD; }

int power_mod(int base, int exp) {
    int result = 1;
    while(exp) {
        if(exp & 1) result = mod_mul(result, base);
        base = mod_mul(base, base);
        exp >>= 1;
    }
    return result;
}

int num_elements, exponent_k;
int factorials[MAX_NUM], inverse_factorials[MAX_NUM];
int prime_powers[MAX_NUM], mobius_values[MAX_NUM];
int primes_list[MAX_NUM / 10], prime_count;
bool is_composite[MAX_NUM];

void sieve_and_precompute(int limit) {
    factorials[0] = 1;
    for(int i = 1; i <= limit; ++i)
        factorials[i] = mod_mul(factorials[i - 1], i);

    inverse_factorials[limit] = power_mod(factorials[limit], MOD - 2);
    for(int i = limit - 1; i >= 0; --i)
        inverse_factorials[i] = mod_mul(inverse_factorials[i + 1], i + 1);

    is_composite[1] = true;
    mobius_values[1] = 1;

    for(int i = 2; i <= limit; ++i) {
        if(!is_composite[i]) {
            primes_list[++prime_count] = i;
            mobius_values[i] = power_mod(i, exponent_k);
        }
        for(int j = 1; j <= prime_count && primes_list[j] * i <= limit; ++j) {
            is_composite[primes_list[j] * i] = true;
            mobius_values[i * primes_list[j]] = mod_mul(mobius_values[i], mobius_values[primes_list[j]]);
            if(i % primes_list[j] == 0) break;
        }
    }
}

int combination(int n, int k) {
    if(k > n || k < 0) return 0;
    return mod_mul(mod_mul(factorials[n], inverse_factorials[k]), inverse_factorials[n - k]);
}

int partial_sum_array[3 * MAX_NUM][3], derived_values[MAX_NUM];

int compute_partial(int m, int d) {
    long long part1 = 1LL * partial_sum_array[d][0] * (m + 1);
    long long part2 = partial_sum_array[d - 1][2] - partial_sum_array[d - m - 1][2];
    long long part3 = 1LL * (partial_sum_array[d - m - 1][1] - partial_sum_array[d - 1][1]) * (d - m - 1);
    long long part4 = -partial_sum_array[d + m][2] + partial_sum_array[d][2];
    long long part5 = 1LL * (partial_sum_array[d + m][1] - partial_sum_array[d][1]) * (d + m + 1);
    return ((part1 + part2 + part3 + part4 + part5) % MOD + MOD) % MOD;
}

void cosmic_radiation_analysis() {
    cin >> num_elements >> exponent_k;

    sieve_and_precompute(num_elements);

    for(int i = 0; i <= num_elements; ++i) {
        if(!((num_elements + i) & 1))
            partial_sum_array[i][0] = combination(num_elements, (num_elements + i) / 2);
    }

    for(int i = 1; i <= num_elements; ++i)
        partial_sum_array[i][1] = mod_add(partial_sum_array[i - 1][1], partial_sum_array[i][0]);

    for(int i = 1; i <= num_elements; ++i)
        partial_sum_array[i][2] = mod_add(partial_sum_array[i - 1][2], mod_mul(partial_sum_array[i][0], i));

    for(int i = num_elements + 1; i <= 3 * num_elements; ++i)
        partial_sum_array[i][1] = partial_sum_array[i - 1][1];

    for(int i = num_elements + 1; i <= 3 * num_elements; ++i)
        partial_sum_array[i][2] = partial_sum_array[i - 1][2];

    derived_values[1] = 2;

    for(int i = 2; i <= num_elements; ++i) {
        long long value = 0;
        value += 1LL * partial_sum_array[0][0] * (i + 1);
        value -= 1LL * partial_sum_array[i + 1][2] * 2;
        value += 1LL * partial_sum_array[i + 1][1] * (i * 2 + 2);

        int step = i + 2, sign = 1;
        while(step <= num_elements + i) {
            if(sign)
                value -= 2LL * compute_partial(i, step);
            else
                value += 2LL * compute_partial(i, step);
            step += i + 2;
            sign ^= 1;
        }

        derived_values[i] = ((value % MOD) + MOD) % MOD;
    }

    for(int i = num_elements; i >= 1; --i)
        derived_values[i] = mod_sub(derived_values[i], derived_values[i - 1]);

    int final_answer = 0;
    for(int i = 1; i <= num_elements; ++i) {
        int diff = mod_sub(derived_values[i], derived_values[i - 1]);
        final_answer = mod_add(final_answer, mod_mul(mobius_values[i], diff));
    }

    cout << final_answer << "\n";
}