DOCSEARCHbyAlgolia
Submit Docs

xiezheyuan's Blog

website·Indexed 29 days ago

https://www.xiezheyuan.xyz/

A technical blog focusing on competitive programming, algorithm analysis, and problem solving. Content includes detailed tutorials on polynomial operations (inversion, exp, ln), number theory (Dirichlet convolution, quadratic residue), and various data structures and techniques such as Mo's algorithm, virtual trees, and dynamic programming.

Tokens
52.7K
Snippets
86
Records
157
Agent score
49%

What's inside xiezheyuan

  2. Introduction to Ordinary and Exponential Generating Functions

    For a function $f: \mathbb{N} \to \mathbb{C}$, two primary types of generating functions are defined:

    1. Ordinary Generating Function (OGF): $\mathbf{F}(z) = \sum_{i \geq 0} f(i)z^i$. It is often denoted as $\langle f(0), f(1), f(2), \dots \rangle$.
    2. Exponential Generating Function (EGF): $\hat{\mathbf{F}}(z) = \sum_{i \geq 0} \frac{f(i)}{i!}z^i$.

    A closed form $g(z)$ exists if there is a set $S \subseteq \mathbb{C}$ such that for all $z \in S$, $F(z)$ converges and can be represented by a finite-term function $g(z)$.

  3. Understand the Symbolic Method for Unlabeled Combinatorial Classes

    The symbolic method models combinatorial objects to derive their Ordinary Generating Functions (OGF). Key basic components include:

    • Neutral object $\epsilon$: Size $|\epsilon|=0$, OGF $\mathbf{E}(z)=1$.
    • Atomic object $\bullet$: Size $|\bullet|=1$, OGF $\mathbf{Z}(z)=z$.
    • Cartesian Product: For $\mathcal{C} = \mathcal{A} \times \mathcal{B}$, the OGF is $\mathbf{C}(z) = \mathbf{A}(z)\mathbf{B}(z)$.
    • Disjoint Union: For $\mathcal{C} = \mathcal{A} \cup \mathcal{B}$, the OGF is $\mathbf{C}(z) = \mathbf{A}(z) + \mathbf{B}(z)$.

  4. Use Dirichlet Generating Functions (DGF) for multiplicative functions

    A Dirichlet Generating Function for a number-theoretic function $f(n)$ is defined as: $\mathbf{F}(z) = \sum_{i \geq 1} f(i)i^{-z}$.

    For a multiplicative function $f(n)$, the DGF can be expressed as an Euler product: $\mathbf{F}(z) = \prod_{p \in \mathbb{P}} \sum_{i \geq 0} f(p^i)p^{-iz}$.

    Crucially, the product of two DGFs corresponds to the Dirichlet convolution of their respective functions: $\mathbf{F}(z) \cdot \mathbf{G}(z) = \sum_{d \geq 1} (f \ast g)(d) \cdot d^{-z}$.

  5. Solve P5320 [BJOI2019] Tiling Summation Problem

    The problem asks for the value of $\frac{1}{r-l+1}\sum_{i=l}^{r}\binom{f(i)}{k} \pmod{998,244,353}$, where $f(n)$ is the number of ways to cover an $m \times n$ grid with $1 \times 2$ dominoes. Constraints are $1 \leq l \leq r \leq 6 \times 10^{18}$, $m \in {2, 3}$, and $1 \leq k \leq 501$.

  6. Solve Athlete Welcome Ceremony problem using 3D DP and Prefix Sums

    The problem asks for the number of ways to replace '?' characters in a string $S$ of length $n$ with characters 'a', 'b', and 'c' such that no two adjacent characters are the same, given constraints on the maximum number of 'a's ($x$), 'b's ($y$), and 'c's ($z$) used.

    Approach:

    1. Use Dynamic Programming: Let $f(i, x, y)$ be the number of ways to fill the prefix $S[1, i]$ using $x$ 'a's and $y$ 'b's, where all remaining '?' are replaced by 'c', ensuring no adjacent characters are identical.
    2. The transition involves iterating through the possible characters for the next position, resulting in a time complexity of $O(n^3)$.
    3. To handle $q$ queries efficiently, use a 3D prefix sum. The answer for a query $(x, y, z)$ is the sum of $f(n, i, j)$ where $i \leq x$, $j \leq y$, and $(C - i - j) \leq z$ (where $C$ is the total number of '?' in the string).
    4. By applying inclusion-exclusion (3D prefix sum), queries can be answered in $O(1)$.

    Complexity:

    • Time: $O(n^3)$ for DP and prefix sum calculation.
    • Space: $O(n^3)$.

  7. Solve Disrupting Communications problem using Tree DP and Rerooting

    The problem asks for the number of connected components that intersect with a given path $(u, v)$ in a tree of $n$ nodes, for $q$ queries.

    Approach:

    1. Root the tree at node 1. If $u=1$, any connected component intersecting the path $(1, v)$ must have its root on the path $(1, v)$.
    2. Let $f(u)$ be the number of connected components rooted at $u$. The transition is straightforward tree DP.
    3. For a query $(1, v)$, the answer is the sum of $f(u)$ for all $u$ on the path from 1 to $v$.
    4. To handle arbitrary $u$, use rerooting DP to calculate $f(u)$ for all possible roots.
    5. Process queries offline by attaching them to one of the path endpoints.
    6. Implementation Detail: When rerooting, if you encounter a division by zero (lack of modular inverse), use a structure to track the number of zero factors.

    Complexity:

    • Time: $O(n \log^2 n)$.

  8. Count labeled weakly connected DAGs using generating functions

    To find the number of labeled weakly connected DAGs $f(n)$ for $n$ nodes, use the relationship between the exponential generating function (EGF) of weakly connected DAGs $\hat{\mathbf{F}}(z)$ and the EGF of all labeled DAGs $\hat{\mathbf{G}}(z)$.

    1. The relationship is $\exp(\hat{\mathbf{F}}(z)) = \hat{\mathbf{G}}(z)$, which implies $\hat{\mathbf{F}}(z) = \ln \hat{\mathbf{G}}(z)$.
    2. To find $g(n)$ (the number of labeled DAGs), use the inclusion-exclusion principle based on the number of nodes with in-degree 0: $g(n) = \sum_{i=1}^{n} \binom{n}{i} g(n-i) (-1)^{i+1} 2^{i(n-i)}$
    3. This recurrence can be transformed into a convolution form by substituting $2^{i(n-i)} = \frac{2^{\binom{n}{2}}}{2^{\binom{i}{2}} 2^{\binom{n-i}{2}}}$.
    4. Define $p(n) = \frac{g(n)}{n! \cdot 2^{\binom{n}{2}}}$ and $q(n) = \frac{(-1)^{n+1}}{n! \cdot 2^{\binom{n}{2}}}$.
    5. The generating functions $\mathbf{P}(z) = \sum p(i)z^i$ and $\mathbf{Q}(z) = \sum q(i)z^i$ satisfy $\mathbf{P}(z) = \frac{1}{1 - \mathbf{Q}(z)}$.
    6. The final result $f(n)$ is obtained by calculating $\hat{\mathbf{G}}(z)$ from $\mathbf{P}(z)$, then computing $\hat{\mathbf{F}}(z) = \ln \hat{\mathbf{G}}(z)$, and multiplying the coefficient of $z^n$ by $n!$.

  9. Solve CF1923F Shrink-Reverse binary string minimization

    The goal is to minimize the binary value of a string $S$ of length $n$ using at most $k$ operations. Two operations are available: swapping any two characters and the 'Shrink-Reverse' transformation (removing all leading zeros and then reversing the string).

    Key algorithmic insights:

    1. Operation Order: All swaps should be performed before the transformation.
    2. Transformation Limit: At most one transformation is necessary. Performing two transformations is equivalent to removing trailing zeros, which can be achieved more optimally by a single transformation combined with strategic swaps.
    3. Case 0 (No Transformation): Use a greedy approach with two pointers to swap high-position '1's with low-position '0's to minimize the value.
    4. Case 1 (One Transformation):
      • Reverse the string and use a Suffix Array to compare potential substrings.
      • Find a window $[L, R]$ such that it contains all '1's that cannot be swapped out (at most $k-1$ '1's outside the window).
      • The window must be large enough to hold the total count of '1's in the original string.
      • Use two pointers to find the shortest valid window. If lengths are equal, use the Suffix Array to find the lexicographically smallest one.
      • Fill the remaining '1's from the back of the window to maintain the smallest value.
    #include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }

template<int N>
struct SuffixArray {
    int sa[N], rk[N], tmp[N];
    void build(const string &s){
        int n = s.size() - 1;
        for(int i=1;i<=n;i++) sa[i] = i, rk[i] = s[i];
        for(int k=1;k<n;k<<=1){
            auto mk = [=](int x){ return make_pair(rk[x], rk[x + k]); };
            sort(sa + 1, sa + n + 1, [mk](int x, int y){ return mk(x) < mk(y); });
            for(int i=1,p=0;i<=n;i++){
                if(mk(sa[i - 1]) == mk(sa[i])) tmp[sa[i]] = p;
                else tmp[sa[i]] = ++p;
            }
            copy(tmp + 1, tmp + n + 1, rk + 1);
        }
    }
};

const int N = 5e5 + 5;
int n, k;
string s;
SuffixArray<N> sa;

// Case 0: No transformation, greedy swap
string solve0(){
    string current_s = ' ' + s;
    int L = 1, R = n;
    string ret = current_s;
    for(int i=1;i<=k;i++){
        while(L <= n && current_s[L] != '1') L++;
        while(R >= 1 && current_s[R] != '0') R--;
        if(L > n || R < 1 || L > R) break;
        swap(ret[L], ret[R]);
        L++, R--;
    }
    return ret;
}

struct node{
    int pos, len;
    bool operator<(const node &rhs) const {
        return len == rhs.len ? sa.rk[pos] < sa.rk[rhs.pos] : len < rhs.len;
    }
};

// Case 1: One transformation
string solve1(){
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    rev_s = " " + rev_s;
    sa.build(rev_s);
    int R = 0, cnt = 0, total = count(rev_s.begin(), rev_s.end(), '1');
    vector<node> vct;
    for(int L=1;L<=n;L++){
        while(R <= n && !((R - L + 1 >= total) && (total - cnt <= k - 1))) cnt += rev_s[++R] == '1';
        if(R > n) break;
        vct.push_back({L, R - L + 1});
        cnt -= rev_s[L] == '1';
    }
    auto [pos, len] = *min_element(vct.begin(), vct.end());
    string ret = rev_s.substr(pos, len);
    int ext = total - count(ret.begin(), ret.end(), '1');
    reverse(ret.begin(), ret.end());
    for(char& ch : ret){
        if(ch == '0' && (--ext) >= 0) ch = '1';
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

string wash(string s){
    size_t first_one = s.find('1');
    if(first_one == string::npos) return "0";
    return s.substr(first_one);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    if(!(cin >> n >> k >> s)) return 0;
    string r1 = wash(solve0()), r2 = wash(solve1()), ans;
    if(r1.size() < r2.size()) ans = r1;
    else if(r1.size() > r2.size()) ans = r2;
    else ans = min(r1, r2);
    int res = 0;
    for(char ch : ans) res = Add(Add(res, res), ch == '1');
    cout << res << '\n';
    return 0;
}

  10. Implement Online Mo's Algorithm for range frequency squares

    The online version of Mo's algorithm for this problem involves:

    1. Preprocessing: Divide the sequence into $B$ blocks. Precompute the answers for all possible combinations of full blocks $O(nB)$ and store the prefix counts of elements for these blocks $O(nB)$.
    2. Handling Updates: When a value is updated, update the prefix count buckets for all blocks following the updated position. Store updates in a log to apply them during queries.
    3. Querying:
      • Identify the nearest full-block range $[L, R]$ that covers the query range $[l, r]$.
      • Update the precomputed answer for the full-block range to the current timestamp by iterating through the update log and applying changes that fall within the block range.
      • Use Mo's double-pointers to move from the full-block range $[L, R]$ to the specific query range $[l, r]$.
      • Use a stack-based bucket (tracer) to track changes during pointer movement to avoid $O(n)$ bucket clearing.

  11. Calculate subset sums divisible by m using root of unity inversion

    To find the number of subsets $S \subseteq [L, R] \cap \mathbb{Z}$ such that $m \mid \sum_{i \in S} i$, the problem can be modeled using generating functions. Let $F(z) = \prod_{k=1}^{n} (1 + z^k)$ where $n = R - L + 1$ (after shifting the range).

    Using the root of unity inversion lemma, the number of subsets with a sum divisible by $m$ is given by: $$\sum_{i \geq 0} [m \mid i] \cdot [z^i] F(z) = \frac{1}{m} \sum_{k=0}^{m-1} F(\omega_m^k)$$ where $\omega_m$ is the $m$-th root of unity.

    Additionally, the problem utilizes the property $F(x, a, b) = \gcd(x^a-1, x^b-1)+1 = x^{\gcd(a,b)}$ for $a, b \neq 0$.

  12. Compute the Minkowski Sum of two lower convex hulls

    The Minkowski sum of two point sets $S$ and $T$ is defined as $S+T = {x+y | x \in S, y \in T}$. For lower convex hulls where x-coordinates are consecutive integers, the lower convex hull of the Minkowski sum is the $(\min, +)$ convolution of the lower convex hulls of $S$ and $T$.

    Because the edges of the resulting convex hull are exactly the union of the edge vectors of the two input hulls, the sum can be computed by:

    1. Extracting the edge vectors (or slopes) of both lower convex hulls.
    2. Sorting these vectors by slope (since they are already sorted in the input hulls, a merge operation is sufficient).
    3. Computing the prefix sums of the sorted vectors to reconstruct the points.

    This reduces the complexity from $O(|S|\cdot|T|)$ to $O(|S|+|T|)$.