Fixed Value Construction: Binary & Fibonacci

Translated to English using AI. For a better reading experience, please visit: https://dk-qwq.github.io/blog/posts/bin-fib-decomposition/

Core Idea: Base Graph + Regulator

Regardless of the fixed-value construction method used, the essence is to construct a logarithmic-level base, and then use a regulator to construct the target fixed value through splitting methods similar to binary or Fibonacci.

1. Binary Decomposition

1. Principle Overview

By observing the value function, construct a base graph of the form $$$f_i = 2 \times f_{i - 1}$$$, obtaining $$$f_i = 2^i$$$. Perform a binary decomposition on the required fixed value, and finally achieve the construction of the fixed value through the regulator.

2. Practice Problems

Codeforces 388B — Fox and Minimal path

Problem Statement Given an integer $$$K$$$ ($$$1 \leq K \leq 10^9$$$), construct an undirected graph such that there are exactly $$$K$$$ paths of the same length from the start vertex to the end vertex.

Solution It is not hard to think of constructing it in the form of diamonds, resulting in $$$2^n$$$ paths of the same length to a single vertex. Then, append paths of fixed lengths respectively so that the lengths of the paths reaching the end vertex are all the same. Finally, perform a binary decomposition on $$$K$$$.

Optimization: How to minimize $$$n$$$? The basic diamond form is still somewhat wasteful. Consider optimizing the base graph into the following form:

The fixed-length paths appended at the end can also reuse chains of length $$$\log_2 V$$$. Through this reuse, the minimum $$$n$$$ can be reduced to the $$$3 \lfloor {\log_2 {V}} \rfloor$$$ level.

Reference submission: https://codeforces.me/contest/388/submission/387215801

AtCoder ABC 108 D — All Your Paths are Different Lengths

Problem Statement Construct a weighted directed graph such that there are exactly $$$L$$$ different paths from $$$1$$$ to $$$N$$$, and their lengths are integers from $$$0$$$ to $$$L - 1$$$.

Solution Assuming we already have paths from $$$S'$$$ to $$$T$$$ with weights in the range $$$[0, 2^{L - 1})$$$, attempt to connect $$$S$$$ and $$$S'$$$ to construct paths from $$$S$$$ to $$$T$$$ with weights in $$$[0, 2^L)$$$.

After trying, we can find that transferring can be completed by adding edges with weights $$$0$$$ and $$$2^{L - 1}$$$ respectively.

By analogy, the number of vertices is $$$2 + \lfloor {\log_2 L} \rfloor = 2 + 19 = 21$$$. Adding a few more edges to optimize away one of the vertices will satisfy the problem requirements.

Reference submission: https://atcoder.jp/contests/abc108/submissions/78452048

2. Fibonacci Decomposition

1. Principle Overview

Construct a Fibonacci sequence of the form $$$F_i = F_{i-1} + F_{i-2}$$$, and split the required fixed value using a reverse-order greedy strategy.

2. Correctness Proof (Zeckendorf's theorem)

Zeckendorf's theorem Any positive integer $$$N$$$ can be uniquely represented as the sum of one or more distinct non-consecutive Fibonacci numbers:

1. Proof of Existence * There exists a $$$k$$$ such that $$$F_k \leq N \lt F_{k+1}$$$, we select $$$F_k$$$. * Since $$$N \lt F_{k + 1} = F_k + F_{k - 1}$$$, we have:

This guarantees that when continuing the greedy decomposition for $$$N'$$$, the next selected Fibonacci number will definitely be less than $$$F_{k-1}$$$, naturally satisfying the non-consecutive condition.

2. Proof of Uniqueness * Lemma: The sum of a subset of non-consecutive Fibonacci numbers no greater than $$$F_n$$$ is strictly less than $$$F_{n + 1}$$$.

• Proof by Contradiction: Assume there are two different decomposition methods for $$$N$$$. Find the largest Fibonacci number whose presence differs between the two sets, denoted as $$$F_k$$$. Without loss of generality, let $$$F_k \in A$$$ and $$$F_k \notin B$$$.
• After removing the common parts greater than $$$F_k$$$ from both sets, the value of the remaining part is denoted as $$$N'$$$.
• At this time, the two decomposition methods for $$$N'$$$ are: $$$N' = F_k + \sum_{F_i \in A, i \lt k} F_i$$$ and $$$N' = \sum_{F_i \in B, i \lt k} F_i$$$.
• According to the lemma, the sum of all non-consecutive Fibonacci numbers less than $$$F_k$$$ in set $$$B$$$ is strictly less than $$$F_k$$$:

• However, in set $$$A$$$, $$$N'$$$ contains at least $$$F_k$$$, meaning $$$N' \geq F_k$$$, which leads to a contradiction. Therefore, the decomposition method must be unique.

3. Practice Problems

2026 Nowcoder Multi-University Training Contest 9A

Problem Statement Let $$$P_1 = 1$$$, and $$$P_v = \sum_{u \rightarrow v} P_u$$$.

We are required to construct a simple undirected graph such that $$$\sum_{u \rightarrow v} (P_u + P_v) = K$$$.

Solution Since it is a simple graph, the edge connection forms should be $$$(i - 2) - i$$$ and $$$(i - 1) - i$$$.

Try this connection method: * For the base graph $$$1, \cdots, b$$$, connect $$$(i - 2) - i$$$ and $$$(i - 1) - i$$$, which yields $$$P_i = F_i$$$. * Let the contribution of the base graph be $$$C_b$$$, then:

Consider how to regulate: * Hanging a node under node $$$i$$$ gives a contribution of $$$2 F_i$$$, which cannot change the parity. * We find that we can adjust the parity minimally by adding a new node connected to base nodes $$$2, 3$$$ to get a contribution of $$$9$$$.

Ultimately we can get: * Find the largest $$$b$$$ such that $$$C_b \leq K$$$. If the remainder is odd, subtract $$$9$$$ first. Divide the remaining even number by $$$2$$$; by Zeckendorf's theorem, it can definitely be decomposed. * If the remainder is odd and less than $$$9$$$, simply let $$$b := b - 1$$$. The required increase in contribution is only $$$3 P_b$$$. Since there is no requirement for them to be non-consecutive, any greedy construction will certainly have a solution.

Suggestions for Selection

• For problems with a small number of vertices, it is recommended to use the binary decomposition method.
• If the problem requires a simple graph and allows a larger number of vertices, it is recommended to use the Fibonacci decomposition method.
• Of course, the best approach is to decide based on the value function of the specific problem.

CF2247F — A More Intuitive Dominator-Tree Solution (Different from the Official Editorial)

This post was AI-translated from Chinese.

If you can read Chinese, I recommend the original Chinese write-up:

https://dk-qwq.github.io/blog/posts/cf2247/cf2247f/

or

https://www.luogu.com.cn/article/3l93nkdh

Problem

You are given a grid graph where you may only move right or down. Each cell is marked with 0/1, indicating whether it is usable. $$$(1,1)$$$ is the start and $$$(n,m)$$$ is the destination.

We need to count how many non-empty sets of cells $$$S$$$ satisfy:

$$$\forall x, y \in S$$$, if a path from $$$(1,1)$$$ to $$$(n,m)$$$ passes through $$$x$$$, then it must also pass through $$$y$$$.

Solution

I want to present a solution that is much easier to come up with than the official one, although it requires a bit more code.

1. Two types of valid sets

A valid set $$$S$$$ can only be of two kinds:

• all cells in $$$S$$$ are blocked / unreachable / not contained in any valid $$$(1,1)\to(n,m)$$$ path;
• all cells in $$$S$$$ are cells that lie on valid paths.

For the first kind, the answer is obviously:

where count is the number of cells that are not on any valid start-to-end path.

So from now on, we only consider the second kind.

2. The relation between two cells

For any two cells $$$x, y$$$ in such a set, we must have:

• every valid path passing through $$$x$$$ also passes through $$$y$$$;
• every valid path passing through $$$y$$$ also passes through $$$x$$$.

This “must pass through” relation is exactly what dominator trees describe.

Since the grid with only right/down moves is a DAG, we can build a dominator tree for:

• the forward graph (from top-left to bottom-right),
• and the reversed graph (equivalently, considering the bottom-right to top-left direction).

Then the relation between $$$x$$$ and $$$y$$$ can be converted into domination relations on the forward and reverse dominator trees.

3. Why DSU works

Checking the domination relation for every pair $$$(x,y)$$$ would be too complicated.

Instead, observe the following:

Suppose

and $$$u$$$ and $$$v$$$ are mutually related (in the sense required by the problem). Then by the definition on the original graph, every path between $$$u$$$ and $$$v$$$ must also pass through $$$w$$$, so $$$w$$$ must belong to the set as well.

This means that the set of mutually related vertices must form a connected chain on the dominator tree, connected through parent-child edges.

Let:

• fa1[u] be the parent of $$$u$$$ in the forward dominator tree,
• fa2[u] be the parent of $$$u$$$ in the reverse dominator tree.

Then the condition that two adjacent vertices are mutually related is equivalent to:

fa2[fa1[u]] == u

So we can simply check this condition for every vertex, and if it holds, merge u with fa1[u] in a DSU.

After that, each DSU component gives one maximal group of mutually valid cells. If a component has size siz, then it contributes:

because any non-empty subset of this component is valid.

So the total contribution from cells that lie on valid paths is:

over all DSU components.

Finally, don’t forget to add the contribution from cells that are not on any valid path:

Be careful not to double count any special edge case.

Complexity

Let $$$V = nm$$$.

Building the two dominator trees on DAGs and processing the DSU takes roughly:

since each grid cell has only constant out-degree.

Submission

#include <bits/stdc++.h>
#include <cassert>
#include <format>
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
using ll = long long;

class DAGDominatorTree {
public:
    // vertices are numbered from 1 to n
    // g[u] contains directed edges u -> v in the original graph
    // the returned dominator tree has size n + 1, where 0 is a virtual root
    vector<vector<int>> build(int n, const vector<vector<int>>& g) {
        this->n = n;
        LOG = __lg(max(1, n)) + 2;

        G.assign(n + 1, {});
        RG.assign(n + 1, {});
        ST.assign(n + 1, {});
        indeg.assign(n + 1, 0);
        dep.assign(n + 1, 0);
        fa.assign(n + 1, vector<int>(LOG, 0));

        // copy the graph and build the reverse graph
        for (int u = 1; u <= n; ++u) {
            for (int v : g[u]) {
                G[u].push_back(v);
                RG[v].push_back(u);
                ++indeg[v];
            }
        }

        // add virtual root: 0 -> all vertices with indegree 0
        for (int u = 1; u <= n; ++u) {
            if (indeg[u] == 0) {
                G[0].push_back(u);
                RG[u].push_back(0);
                ++indeg[u];
            }
        }

        topoBuild();

        // build the dominator tree
        for (int u = 1; u <= n; ++u) {
            ST[fa[u][0]].push_back(u);
        }
        return ST;
    }

private:
    int n, LOG;
    vector<vector<int>> G, RG, ST, fa;
    vector<int> indeg, dep;

    int lca(int x, int y) {
        if (x == 0 || y == 0) return x | y;  // 0 acts as “null”
        if (dep[x] < dep[y]) swap(x, y);

        int d = dep[x] - dep[y];
        for (int k = 0; k < LOG; ++k) {
            if (d >> k & 1) x = fa[x][k];
        }

        if (x == y) return x;

        for (int k = LOG - 1; k >= 0; --k) {
            if (fa[x][k] != fa[y][k]) {
                x = fa[x][k];
                y = fa[y][k];
            }
        }
        return fa[x][0];
    }

    void topoBuild() {
        queue<int> q;
        q.push(0);  // virtual root first

        int cnt = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ++cnt;

            if (u != 0) {
                int p = 0;
                for (int pre : RG[u]) p = lca(p, pre);

                fa[u][0] = p;
                dep[u] = dep[p] + 1;

                for (int k = 1; k < LOG; ++k) {
                    fa[u][k] = fa[fa[u][k - 1]][k - 1];
                }
            }

            for (int v : G[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }

        // the original graph is not a DAG
        if (cnt != n + 1) {
            throw runtime_error("Input graph is not a DAG.");
        }
    }
};

struct DSU{
    vector<int> fa, siz;
    void init(int n) {
        fa.assign(n + 1, 0), siz.assign(n + 1, 1);
        siz[0] = 0;
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x? x: fa[x] = find(fa[x]);
    }
    bool Union(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(siz[x] > siz[y]) swap(x, y);
        fa[x] = y, siz[y] += siz[x];
        return true;
    }
}D;

const ll mod = 998244353;
ll qpow(ll x, ll k) {
    ll res = 1;
    while(k) {
        if(k & 1ll) res = res * x % mod;
        k >>= 1, x = x * x % mod;
    }
    return res;
}

void solve() {
    DAGDominatorTree solver;

    int n, m; cin >> n >> m;
    int N = n * m;
    auto encode = [&](int x, int y) -> int{
        return (x - 1) * m + y;
    };
    auto decode = [&](int S) -> string {
        int x = S / m, y = S % m;
        if(y == 0) x--, y += m;
        return format("({}, {})", x + 1, y);
    };

    vector a(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++) {
        string s; cin >> s;
        for(int j = 1; j <= m; j++)
            a[i][j] = s[j - 1] - '0';
    }

    vector reach(n + 1, vector<bool>(m + 1, false));
    reach[1][1] = true;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        if(a[i][j] == 0) continue;
        if(reach[i - 1][j] || reach[i][j - 1])
            reach[i][j] = true;
    }

    if(!reach[n][m]) {
        return cout << qpow(2, n * m) - 1 << endl, void();
    }

    vector g(N + 1, vector<int>());
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        if(!reach[i][j]) continue;
        if(reach[i - 1][j])
            g[encode(i - 1, j)].push_back(encode(i, j));
        if(reach[i][j - 1])
            g[encode(i, j - 1)].push_back(encode(i, j));
    }

    vector reach2(n + 1 + 1, vector<bool>(m + 1 + 1, false));
    reach2[n][m] = true;
    for(int i = n; i >= 1; i--) for(int j = m; j >= 1; j--) {
        if(a[i][j] == 0) continue;
        if(reach2[i + 1][j] || reach2[i][j + 1])
            reach2[i][j] = true;
    }


    vector gg(N + 1, vector<int>());
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        if(!reach2[i][j]) continue;
        if(reach2[i - 1][j])
            gg[encode(i, j)].push_back(encode(i - 1, j));
        if(reach2[i][j - 1])
            gg[encode(i, j)].push_back(encode(i, j - 1));
    }

    auto ST1 = solver.build(N, g);

    auto ST2 = solver.build(N, gg);

    vector<int> fa1(N + 1, 0);
    vector<int> fa2(N + 1, 0);

    for(int u = 1; u <= N; u++) for(auto v: ST1[u])
        fa1[v] = u;
    for(int u = 1; u <= N; u++) for(auto v: ST2[u])
        fa2[v] = u;

    D.init(N);
    for(int u = 1; u <= N; u++) {
        if(fa2[fa1[u]] != u) continue;
        assert(fa1[u] > 0);
        D.Union(u, fa1[u]);
    }

    ll ans = 0;

    vector<bool> vis(N + 1, false);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        if(!reach[i][j] || !reach2[i][j]) continue;
        int r = D.find(encode(i, j));
        if(vis[r]) continue;
        vis[r] = true;
        int sz = D.siz[r];
        ans += qpow(2, sz) - 1;
        ans %= mod;
    }

    int count = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)
        if(!reach[i][j] || !reach2[i][j]) count++;

    if(count)
        cout << (ans + qpow(2, count) - 1) % mod << endl;
    else
        cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while(T--) solve();
}