Directed Edge Orientation with Out-Degree Constraint

Given an undirected graph, determine the number of ways to orient all edges such that every vertex has an out-degree of exactly 1. The result should be modulo 998244353.

For such an orientation to exist, the number of edges must exactly equal the number of vertices, i.e., m = n. Furthermore, every connected component must be a single cycle where each vertex has degree 2. In a cycle of length L, there are exactly two valid orientations (clockwise and counter-clockwise). Thus, the total number of valid configurations is 2^c, where c is the number of disjoint cycles in the graph.

We can identify the cycles by performing a Depth-First Search. For each component, we verify if its edge count equals twice its vertex count. If any component fails this condition, the answer is 0. During the DFS, edges that are not part of the spanning tree correspond to the back-edges completing the cycles. Each such back-edge indicates a cycle, contributing a multiplicative factor of 2 to the answer.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int node_cnt, edge_cnt;
vector<vector<pair<int, int>>> adj;
vector<bool> visited;
vector<bool> in_tree;

void dfs(int u, int parent_edge) {
    visited[u] = true;
    node_cnt++;
    for (auto& p : adj[u]) {
        int v = p.first;
        int eid = p.second;
        edge_cnt++;
        if (eid == parent_edge) continue;
        if (!visited[v]) {
            in_tree[eid] = true;
            dfs(v, eid);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    visited.resize(n + 1, false);
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    
    if (n != m) {
        cout << 0 << endl;
        return 0;
    }
    
    in_tree.resize(m, false);
    long long ans = 1;
    
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            node_cnt = 0;
            edge_cnt = 0;
            dfs(i, -1);
            if (edge_cnt != node_cnt * 2) {
                cout << 0 << endl;
                return 0;
            }
        }
    }
    
    for (int i = 0; i < m; ++i) {
        if (!in_tree[i]) {
            ans = (ans * 2) % MOD;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Permutation LCM Summation with Power Factor

For a permutation P, its value is defined as the k-th power of the least common multiple (LCM) of all its cycle lengths. Given n and k, compute the sum of values over all permutations of size n, modulo 998244353.

We can iterate over all valid cycle type partitions of the permutation. A cycle type is represented by a sequence {a_1, a_2, ..., a_n} where a_i denotes the number of cycles of length i, satisfying sum(i * a_i) = n.

For a fixed cycle type, the number of permutations matching this type can be computed combinatorially. Let f(c, l) be the number of ways to form c cycles of length l from c * l available elements. This is given by:

This function can be precomputed using dynamic programming and factorials.

We use a recursive depth-first search to generate all valid partitions. At each step, we decide the number of cycles c for a given length l, ensuring we do not exceed the remaining elements. We maintain the current LCM and the accumulated product of combinatorial terms. When all n elements are assigned, the contribution to the total sum is the product of the permutation count and the k-th power of the LCM.

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 998244353;

long long power(long long base, long long exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int n, k;
long long total_ans = 0;
vector<long long> fact, inv_fact, pow_k;
vector<vector<long long>> comb, cycle_ways;

void precompute() {
    fact.resize(n + 1);
    inv_fact.resize(n + 1);
    pow_k.resize(n + 1);
    comb.resize(n + 1, vector<long long>(n + 1));
    
    fact[0] = inv_fact[0] = pow_k[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        inv_fact[i] = power(fact[i], MOD - 2);
        pow_k[i] = power(i, k);
    }
    
    for (int i = 0; i <= n; ++i) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
        }
    }
    
    cycle_ways.resize(n + 1, vector<long long>(n + 1, 0));
    for (int l = 1; l <= n; ++l) {
        cycle_ways[0][l] = 1;
        for (int c = 1; c * l <= n; ++c) {
            cycle_ways[c][l] = (cycle_ways[c - 1][l] * comb[c * l][l] % MOD * fact[l - 1] % MOD) % MOD;
        }
        for (int c = 1; c * l <= n; ++c) {
            cycle_ways[c][l] = (cycle_ways[c][l] * inv_fact[c]) % MOD;
        }
    }
}

void search_partitions(int remaining, int min_len, long long curr_lcm, long long curr_ways) {
    if (remaining == 0) {
        total_ans = (total_ans + curr_ways * pow_k[curr_lcm]) % MOD;
        return;
    }
    if (min_len > n || remaining < min_len) return;
    
    search_partitions(remaining, min_len + 1, curr_lcm, curr_ways);
    
    long long lcm_factor = min_len / __gcd(curr_lcm, (long long)min_len);
    for (int c = 1; c * min_len <= remaining; ++c) {
        long long new_lcm = curr_lcm * lcm_factor;
        long long new_ways = curr_ways * comb[remaining][c * min_len] % MOD * cycle_ways[c][min_len] % MOD;
        new_ways = new_ways * pow_k[lcm_factor] % MOD;
        search_partitions(remaining - c * min_len, min_len + 1, new_lcm, new_ways);
        lcm_factor = 1;
    }
}

int main() {
    cin >> n >> k;
    precompute();
    search_partitions(n, 1, 1, 1);
    cout << total_ans << endl;
    return 0;
}

Dynamic Programming for Interval Partitioning

Given an array of n integers, determine the number of ways to partition the elements into several non-empty groups such that the sum of the ranges (max - min) of each group does not exceed m. The result is modulo 1000000007.

Sort the array in ascending order. By processing the elements from smallest to largest, we can apply a dynamic programming approach with early computation of costs. Define dp[i][j][s] as the number of configurations for the first i elements, having j active (unclosed) groups, with a total accumulated range sum of s.

An active group is one that has already received its minimum element but has not yet received its maximum element. When we add the i-th element with value A[i], the difference Delta = A[i] - A[i-1] is added to the range of all j active groups. This immediately contributes j * Delta to the total range sum, which we account for during the state transition.

The transitions for adding A[i] are: - Adding to an existing active group without closing it: multiplies the state count by j. - Adding to an existing active group and closing it: multiplies the state count by 1, and reduces the number of active groups by 1. - Starting a new active group with A[i] as its minimum: increases the number of active groups by 1. - Starting a new group and immediately closing it (a group of size 1 with range 0): leaves the number of active groups unchanged.

Combining these transitions, the DP update is:

The final answer is the sum of dp[n][0][s] for all 0 <= s <= m.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end());
    
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(m + 1, 0)));
    dp[1][0][0] = 1;
    dp[1][1][0] = 1;
    
    for (int i = 2; i <= n; ++i) {
        int delta = arr[i - 1] - arr[i - 2];
        for (int j = 0; j <= i; ++j) {
            for (int s = 0; s <= m; ++s) {
                if (s >= j * delta) {
                    dp[i][j][s] = (dp[i][j][s] + (long long)dp[i - 1][j][s - j * delta] * (j + 1)) % MOD;
                }
                if (s >= (j + 1) * delta) {
                    dp[i][j][s] = (dp[i][j][s] + (long long)dp[i - 1][j + 1][s - (j + 1) * delta] * (j + 1)) % MOD;
                }
                if (j > 0 && s >= (j - 1) * delta) {
                    dp[i][j][s] = (dp[i][j][s] + dp[i - 1][j - 1][s - (j - 1) * delta]) % MOD;
                }
            }
        }
    }
    
    int ans = 0;
    for (int s = 0; s <= m; ++s) {
        ans = (ans + dp[n][0][s]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Optimized State Tracking for Card Operations

There are 3n cards, each with a value in the range [1, n]. The operation consists of taking the 5 leftmost cards, rearranging them in any order, and deleting the 3 leftmost cards from this rearranged sequence. If the 3 deleted cards have the same value, a score of 1 is awarded. When fewer than 5 cards remain, if the final 3 cards are equal, a score of 1 is awarded. Find the maximum possible score.

A naive dynamic programming approach defines dp[i][u][v] as the maximum score after i operations, where u and v are the two remaining buffered cards. This leads to O(n^3) states and transitions, which is computationally infeasible for n = 2000.

To optimize, we observe that the buffer cards u and v must originate from the sequence of cards already processed. Since we process the array in blocks of 3 cards, at each step the set of available cards consists of the two buffered cards and the next 3 cards from the array. If the 3 newly drawn cards are identical, we can directly increment the score by 1 without altering the buffered state.

When the 3 new cards are not identical, any valid triplet to delete must include at least one of the buffered cards. The remaining two cards become the new buffer. This implies that the new buffer states are strictly determined by combinations of the current 5 cards. Consequently, the number of distinct reachable buffer states at each step is bounded by a small constant, and the total number of unique states throughout the process is O(n). By maintaining a sparse representation of the DP table—only tracking reachable (u, v) pairs—we drastically reduce the time and space complexity.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    int total_cards = 3 * n;
    vector<int> cards(total_cards);
    for (int i = 0; i < total_cards; ++i) cin >> cards[i];
    
    if (total_cards == 3) {
        cout << (cards[0] == cards[1] && cards[1] == cards[2] ? 1 : 0) << endl;
        return 0;
    }
    
    map<pair<int, int>, int> curr_dp;
    vector<int> first_five(cards.begin(), cards.begin() + 5);
    
    for (int i = 0; i < 5; ++i) {
        for (int j = i + 1; j < 5; ++j) {
            for (int k = j + 1; k < 5; ++k) {
                vector<int> remaining;
                for (int l = 0; l < 5; ++l) {
                    if (l != i && l != j && l != k) remaining.push_back(first_five[l]);
                }
                int score = (first_five[i] == first_five[j] && first_five[j] == first_five[k]) ? 1 : 0;
                pair<int, int> new_state = {remaining[0], remaining[1]};
                if (curr_dp.count(new_state)) {
                    curr_dp[new_state] = max(curr_dp[new_state], score);
                } else {
                    curr_dp[new_state] = score;
                }
            }
        }
    }
    
    for (int idx = 5; idx <= total_cards - 4; idx += 3) {
        map<pair<int, int>, int> next_dp;
        int c1 = cards[idx], c2 = cards[idx + 1], c3 = cards[idx + 2];
        
        for (auto& state : curr_dp) {
            int u = state.first.first;
            int v = state.first.second;
            int base_score = state.second;
            
            vector<int> hand = {u, v, c1, c2, c3};
            for (int i = 0; i < 5; ++i) {
                for (int j = i + 1; j < 5; ++j) {
                    for (int k = j + 1; k < 5; ++k) {
                        vector<int> rem;
                        for (int l = 0; l < 5; ++l) {
                            if (l != i && l != j && l != k) rem.push_back(hand[l]);
                        }
                        int score = base_score + ((hand[i] == hand[j] && hand[j] == hand[k]) ? 1 : 0);
                        pair<int, int> new_state = {rem[0], rem[1]};
                        if (next_dp.count(new_state)) {
                            next_dp[new_state] = max(next_dp[new_state], score);
                        } else {
                            next_dp[new_state] = score;
                        }
                    }
                }
            }
        }
        curr_dp = next_dp;
    }
    
    int max_ans = 0;
    int last_card = cards[total_cards - 1];
    
    for (auto& state : curr_dp) {
        int u = state.first.first;
        int v = state.first.second;
        int base_score = state.second;
        if (u == v && v == last_card) {
            max_ans = max(max_ans, base_score + 1);
        } else {
            max_ans = max(max_ans, base_score);
        }
    }
    
    cout << max_ans << endl;
    return 0;
}