核心思想：基础图 + 调节器#
无论是哪种定值构造方法，本质都是通过构造对数级别的基底，然后通过调节器使用类似二进制或斐波那契的拆分方法来构造出目标定值。
一、二进制拆分法#
1. 原理简述#
通过观察价值函数，构造形如 fi=2×fi−1 的基础图，得到 fi=2i。对所需的定值进行二进制拆分，最后通过调节器来实现定值的构造。
2. 习题#
题意
给定一个整数 K（1≤K≤109），构造一个无向图，使得从起点到终点恰好有 K 条长度相同的路径。
题解
不难想到使用菱形的形式构造，使得到达单点有 2n 条相同长度的路径。然后在后面分别拼接上定长的路径，使得到达终点路径长度均相同，最后对 K 进行二进制拆分即可。
基础的菱形形式依然有些浪费，考虑如下形式优化基础图：
后面拼接的定长路径也可以复用 log2V 长度的链。通过这种复用，最小的 n 可以做到 3⌊log2V⌋ 级别。
参考提交：https://codeforces.com/contest/388/submission/387215801
题意
构造一个带权有向图，使得从 1 到 N 恰好有 L 条不同的路径，且长度是 0 到 L−1 的整数。
n≤20,m≤60,2≤L≤106
题解
假设我们已经有从 S′ 到 T 权值在 [0,2L−1) 范围内的路径，尝试将 S 与 S′ 连接起来，构造出从 S 到 T 的 [0,2L) 路径。
经过尝试可以发现，分别连权值为 0 和 2L−1 的边即可完成转移。
以此类推，点数为 2+⌊log2L⌋=2+19=21。多连几条边优化掉其中一个点即可满足题意。
参考提交：https://atcoder.jp/contests/abc108/submissions/78452048
二、斐波那契拆分法#
1. 原理简述#
构造 Fi=Fi−1+Fi−2 形式的斐波那契数列，通过倒序贪心的方式对所需的定值进行拆分。
2. 正确性证明 (Zeckendorf’s theorem)#
Zeckendorf’s theorem
任何正整数 N 都可以唯一表示为若干个互不相邻的斐波那契数之和：
N=i=1∑kFci(c1≥1,ci+1≥ci+2)1. 存在性证明
- 存在 k 使得 Fk≤N<Fk+1，我们选定 Fk。
- 因为 N<Fk+1=Fk+Fk−1，所以有：
N′=N−Fk<Fk−1
这保证了对 N′ 继续贪心分解时，其选定的下一项斐波那契数必定小于 Fk−1，天然满足不相邻的条件。
2. 唯一性证明
- 引理：由不大于 Fn 且互不相邻的斐波那契数列构成的子集和，严格小于 Fn+1。
i≤n∑Fci≤Fn+Fn−2+Fn−4+⋯+F1=Fn+1−1<Fn+1
- 反证法：假设存在两种不同的 N 分解方式，找出最大的且在两个集合中存在性不同的斐波那契数，记为 Fk。不妨设 Fk∈A 且 Fk∈/B。
- 删掉两个集合中大于 Fk 的公共部分后，剩余部分的值记为 N′。
- 此时 N′ 的两种分解方式为：N′=Fk+∑Fi∈A,i<kFi 以及 N′=∑Fi∈B,i<kFi。
- 根据引理，集合 B 中所有小于 Fk 且不相邻的斐波那契数之和严格小于 Fk：
N′=Fi∈B,i<k∑Fi<Fk
- 但在集合 A 中，N′ 至少包含了 Fk，即 N′≥Fk，这就得出了矛盾。故分解方式必然唯一。
3. 习题#
题意
记 P1=1,Pv=∑u→vPu。
要求构造一个简单无向图，使得 ∑u→v(Pu+Pv)=K。
n≤200,m≤300,K≤1018
题解
由于为简单图，连边形式应为 (i−2)−i,(i−1)−i。
尝试此种连边方式：
-
基础图 1,⋯,b 之间连接 (i−2)−i,(i−1)−i，则有 Pi=Fi。
-
记基础图贡献为 Cb，则：
Cb−Cb−1=2Pb+Pb−1+Pb−2=3Pb考虑如何调节：
-
在节点 i 下挂一个节点的贡献为 2Fi，不能改变奇偶性。
-
发现最小可以通过新增点连接基础点 2,3 得到 9 的贡献来调节奇偶性。
最终可以得到：
