# 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/](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](https://codeforces.me/problemset/problem/388/B)↵
↵
**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](https://codeforces.me/contest/388/submission/387215801)↵
↵
#### [AtCoder ABC 108 D — All Your Paths are Different Lengths](https://atcoder.jp/contests/abc108/tasks/arc102_b)↵
↵
**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$.↵
↵
$$n \leq 20, m \leq 60, 2 \leq L \leq 10^6$$↵
↵
**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](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:↵
↵
$$N = \sum_{i=1}^k F_{c_i} \quad (c_1 \ge 1, \; c_{i+1} \ge c_i + 2)$$↵
↵
**1. Proof of Existence**↵
* There exists a $k$ such that $F_k \leq N < F_{k+1}$, we select $F_k$.↵
* Since $N < F_{k + 1} = F_k + F_{k - 1}$, we have:↵
$$N' = N - F_k < F_{k - 1}$$↵
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}$.↵
$$\sum_{i \leq n} F_{c_i} \leq F_n + F_{n - 2} + F_{n - 4} + \cdots + F_1 = F_{n + 1} - 1 < 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<k} F_i$ and $N' = \sum_{F_i \in B, i<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$:↵
$$N' = \sum_{F_i \in B, i<k} F_i < 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](https://ac.nowcoder.com/acm/contest/133884/A)↵
↵
**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$.↵
↵
$$n \leq 200, m \leq 300, K \leq 10^{18}$$↵
↵
**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:↵
$$C_b - C_{b - 1} = 2 P_b + P_{b - 1} + P_{b - 2} = 3 P_b$$↵
↵
**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.
↵
*Translated to English using AI. For a better reading experience, please visit: [https://dk-qwq.github.io/blog/posts/bin-fib-decomposition/](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](https://codeforces.me/problemset/problem/388/B)↵
↵
**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](https://codeforces.me/contest/388/submission/387215801)↵
↵
#### [AtCoder ABC 108 D — All Your Paths are Different Lengths](https://atcoder.jp/contests/abc108/tasks/arc102_b)↵
↵
**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$.↵
↵
$$n \leq 20, m \leq 60, 2 \leq L \leq 10^6$$↵
↵
**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](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:↵
↵
$$N = \sum_{i=1}^k F_{c_i} \quad (c_1 \ge 1, \; c_{i+1} \ge c_i + 2)$$↵
↵
**1. Proof of Existence**↵
* There exists a $k$ such that $F_k \leq N < F_{k+1}$, we select $F_k$.↵
* Since $N < F_{k + 1} = F_k + F_{k - 1}$, we have:↵
$$N' = N - F_k < F_{k - 1}$$↵
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}$.↵
$$\sum_{i \leq n} F_{c_i} \leq F_n + F_{n - 2} + F_{n - 4} + \cdots + F_1 = F_{n + 1} - 1 < 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<k} F_i$ and $N' = \sum_{F_i \in B, i<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$:↵
$$N' = \sum_{F_i \in B, i<k} F_i < 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](https://ac.nowcoder.com/acm/contest/133884/A)↵
↵
**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$.↵
↵
$$n \leq 200, m \leq 300, K \leq 10^{18}$$↵
↵
**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:↵
$$C_b - C_{b - 1} = 2 P_b + P_{b - 1} + P_{b - 2} = 3 P_b$$↵
↵
**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.
