Factorization into Factorial Divisors

Given integers (n) and (m) where (1 \le m \le n!) and (n \le 20), decompose (m) into a sum of at most (n) divisors of (n!). A solution is guaranteed to exist.

Define a sequence (d_i = \frac{n!}{i!}) for (i) from 1 to (n). By iterating downwards from (i=n) to (1) and greedily subtracting the largest possible multiple of (d_i) from (m), we construct the required set of factors. The count of factors generated is at most (n).

The time complexity is (O(Tn)) for (T) test cases.

#include <iostream>
using namespace std;

long long factorial[21];

void precompute() {
    factorial[0] = 1;
    for (int i = 1; i <= 20; ++i)
        factorial[i] = factorial[i - 1] * i;
}

int main() {
    precompute();
    int t;
    cin >> t;
    while (t--) {
        long long n, m;
        cin >> n >> m;
        long long components[25];
        int idx = 0;
        for (int i = n; i >= 1 && m > 0; --i) {
            long long divisor = factorial[n] / factorial[i];
            if (m >= divisor) {
                long long val = (m / divisor) * divisor;
                components[idx++] = val;
                m -= val;
            }
        }
        cout << idx << "\n";
        for (int i = 0; i < idx; ++i)
            cout << components[i] << " \n"[i == idx - 1];
    }
    return 0;
}

Cosmic Ray Simulation

Given a permutation (T) of size (n) and (m) auxiliary permutations (P_j), the goal is to select a subset of indices (S) from (T) to maximize the score. The value of an index (i) in (T) is (2^{n - T_i}).

The process involves iterating through the permutation (T). When an index (i) is selected (added to (S)), its value is added to the total score. Simultaneously, for every auxiliary permutation (P_j) where (j) matches the current count of selected elements, the first valid (non-deleted) element in (P_j) is marked as deleted.

A subset (S) is valid if, for every auxiliary permutation (P_j) (where (j \le m)), the number of deleted elements within the first (j) steps does not exceed (j). The optimal strategy is to attempt adding elements from (1) to (n). If adding a element (i) keeps the set valid (checked via simulation), it is included.

Constraints: (3 \le n \le 600), (1 \le m \le \lfloor (n-1)/2 \rfloor). The array defining which (P_j) to use is strictly increasing.

Time complexity: (O(n^3)) assuming (n) and (m) are of similar magnitude.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 605;

int n, m;
int power_val[MAXN];
bool is_active[MAXN];
int perm_data[MAXN][MAXN];
bool chosen[MAXN];

int mod_pow(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp & 1) res = 1LL * res * base % MOD;
        base = 1LL * base * base % MOD;
        exp >>= 1;
    }
    return res;
}

bool isValid() {
    bool deleted[MAXN] = {false};
    int current_count = 0;
    for (int i = 1; i <= n - m; ++i) {
        if (!is_active[i]) continue;
        for (int j = 1; j <= n; ++j) {
            int elem = perm_data[i][j];
            if (deleted[elem]) continue;
            deleted[elem] = true;
            if (!chosen[elem]) break;
            current_count++;
        }
        if (current_count > i) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    power_val[n] = 1;
    for (int i = n - 1; i >= 1; --i)
        power_val[i] = (2LL * power_val[i + 1]) % MOD;
        
    for (int i = 1; i <= m; ++i) {
        int x; cin >> x;
        is_active[x] = true;
    }
    for (int i = 1; i <= n - m; ++i) {
        if (!is_active[i]) continue;
        for (int j = 1; j <= n; ++j)
            cin >> perm_data[i][j];
    }
    
    for (int i = 1; i <= n; ++i) {
        chosen[i] = true;
        if (!isValid()) chosen[i] = false;
    }
    
    int total_score = 0;
    for (int i = 1; i <= n; ++i)
        if (chosen[i]) total_score = (total_score + power_val[i]) % MOD;
        
    cout << total_score << "\n";
    return 0;
}

Infinite Binary String Construction

Construct an infinite binary string (S). For (n) intervals ([l_i, r_i]) with color (c_i \in {0, 1}), define (b_i = 1) if all characters in (S[l_i \dots r_i]) equal (c_i). Count the number of distinct possible arrays (b). Results modulo (998244353).

Sort segments by right endpoint. Define (dp[i][c]) as the number of ways where the (i)-th segment is the last chosen one and has color (c). Transition by finding the previous segmant (j) with color (1-c) such that (r_j < l_i). The number of ways is the sum over valid (j) of (dp[j][1-c] \times 2^{cnt}), where (cnt) is the number of segments with color (c) starting after (r_j).

To optimize, maintain a data structure (segment tree) for prefix sums of (dp) values adjusted by powers of 2, allowing (O(n \log n)) complexity.

Tree Partitioning into Continuous Blocks

Given a tree with (n) nodes, for each (x \in [0, k-1]), count ways to remove (x) edges so the resulting (x+1) components have node IDs that form continuous intervals after relabeling.

• Small n ((\le 20)): Brute force enumeration of edges.
• Chain Case: The answer for (x) is simply (\binom{n-1}{x}).
• Min-Heap Tree: Only consider parent edges. A segment ([l, r]) is valid if only one edge connects it to the out side. Process nodes in reverse order, maintaining valid transition points using a set.
• General Case: Dynamic programming on the tree structure or prefix optimization depending on constraints. For (n \le 2 \times 10^5) and (k \le 400), the solution involves specific structural properties of the tree.