企业官网建设流程全解析

成都站的G题Expanding Array，赛场上卡了我挺久。当时读题的感觉是：操作很简单，但能生成的数组数量好像会爆炸，根本不敢往枚举方向想。赛后冷静下来重新推导，才发现这题本质上是一道二叉树计数题，核心结论甚至短到只剩一句话：每个相邻间隙的贡献，只由差值二进制末尾0的个数决定。如果你也是准备ICPC、CCPC或者各种区域赛的选手，这题的思路很值得记一下。

先说这题适合谁：它适合已经能熟练写基础DP、图论模板，但遇到“看似无限过程”的计数题容易慌的选手。题目给出的操作非常朴素，难的是把“无限多中间状态”压缩成一个递推式。下面我按赛后复盘的顺序，把题意、关键性质、递推推导、代码实现和现场踩过的坑全部拆开讲。

1. 题意拆解：一个看起来会爆炸的过程

1.1 操作定义与“最终数组”

题目给了一个长度为 n 的整数数组。你每次可以选择相邻的两个数 x 和 y，要求它们中间能插入一个整数中点。更具体一点：如果 x 和 y 奇偶性相同，那么它们中间的那个整数就是 (x+y)/2，你可以把它插入到两者之间；如果 x 和 y 奇偶性不同，说明两者之间没有整数中点，这次操作就无法进行。重复任意次操作之后，问一共能得到多少种不同的数组。

这个定义非常像“把一个区间不断对半细分”。比如数组 [0,4]，0 和 4 都是偶数，中间整数是 2，所以可以先变成 [0,2,4]；接下来 0 和 2 之间可以插入 1，2 和 4 之间可以插入 3，于是又可以得到 [0,1,2,4] 和 [0,2,3,4]；再操作一步就变成 [0,1,2,3,4]。整个过程确实很像把一条线段不断二分。

这里有个容易忽略的约定：我们只关注“最后得到的数组”是什么，不关注“通过什么顺序得到它”。比如先插 1 再插 2，和先插 2 再插 1，最终得到的都是 [0,1,2,4]，这只能算同一种数组。也就是说，一个数组本质上对应一个“已插入点集合”。这个约定在后面推导递推式时非常重要。

从 [0,4] 出发，把所有可能结果列出来其实只有 5 种：

• [0,4]：什么都不做。
• [0,2,4]：只插入中点 2。
• [0,1,2,4]：插入 2 和 1。
• [0,2,3,4]：插入 2 和 3。
• [0,1,2,3,4]：插入 2、1、3。

这个例子意味着，即使是长度为 4 的单个间隙，状态数也不是 1，而是 5。如果数组长度稍微大一点，比如 [0,8]，手算就很容易漏，这也是这题真正麻烦的地方。

1.2 相邻间隙互相独立

第一次读题，很容易被“数组是整体变化的”这个直觉带偏，以为要做一个超级复杂的全局DP。但其实只要想清楚一件事，整道题就瞬间简化了：初始数组里任意两个相邻元素构成一个“间隙”，之后的插入操作永远只会在某个间隙内部发生，间隙之间互不干涉。

为什么？因为数组里的原始元素永远不会被删除。比如初始数组是 [0, 4, 8]，那么 4 这个元素始终存在。无论你在 0 和 4 之间插入什么，在 4 和 8 之间插入什么，插入点都不可能越过 4 跑到另一侧去。相邻元素如果要进行插入操作，它们要么都属于第一个间隙，要么都属于第二个间隙，不存在一个点同时属于两个间隙的情况。

于是整个问题可以用乘法原理拆开：最终数组的状态，等于第一个间隙选择一个局部状态，第二个间隙选择一个局部状态，第三个间隙选择……然后按顺序拼接起来。所以答案就是所有间隙局部状态数的乘积。这个“间隙独立”的观察是全场第一个关键突破口，也是后面所有推导的地基。

2. 核心观察：一切只看差值的奇偶性

2.1 第一次插入的中点一定是唯一点

对于一个当前相邻对 (L, R)，如果它们之间还能插入，那么能够插入的数是多少？答案只有一个：(L+R)/2，也就是线段的几何中点。比如区间 [0, 4]，中点只能是 2；区间 [0, 8]，中点只能是 4；区间 [1, 7]，中点只能是 4。

这不是“可以选择多个候选点”的问题，而是完完全全确定性的：相邻对只有一对，中点只有一个。所以第一步操作（如果要做）是强制性的，没有任何自由度。自由度出现在中点插入之后：左右两个子区间 [L, mid] 和 [mid, R] 各自可以继续决定插不插、怎么插。

这个观察把所有“看似无穷的扩展”变成了一个递归结构：每次分裂都把一个长区间劈成两个长度减半的子区间。如果你在纸上把这个过程画出来，它就是一株完美的二叉树，根节点是整个区间，左孩子和右孩子分别是左右两个半区间。不同数组就是这棵树上“选了一部分节点插入”的结果。

很多人会在这里想当然地认为“我可以先插入非中点的位置”，但这是不可能的。比如 [0, 4]，你第一步不可能直接插入 1，因为 1 在 0 和 4 之间并不是中点，当前相邻对是 0 和 4，唯一匹配的操作就是插入 2。必须先有 2，才有可能让 0 和 2 变成相邻对，从而插入 1。这个先后关系本质上是树上的祖先关系。

2.2 状态数量为什么只依赖区间长度

接下来一个更关键的化简化是：一个间隙能产生多少局部状态，只取决于它的长度 d = R - L，和 L、R 本身的具体值无关。

有人可能会担心奇偶性问题：区间 [0, 4] 的中点 2 是整数，区间 [1, 5] 的中点 3 也是整数，区间 [0, 5] 的中点 2.5 不是整数，所以 [0,5] 完全不能操作。但这个“能不能操作”本身也只看长度奇偶性：d 是奇数时，L 和 R 奇偶性必然不同，中点必然是 .5 结尾；d 是偶数时，中点必然是整数。至于 L 是奇数还是偶数，并不会改变“中点是不是整数”这件事。

每一次分裂后，左右两个子区间的长度都变成 d/2。继续往下看，子区间能不能继续分裂，又只取决于 d/2 的奇偶性。所以整个递归过程从头到尾都只需要一个参数 d。这样一来，状态数可以记为 f(d)，表示长度为 d 的单个间隙能产生的局部数组数量，复杂度直接从二维区间状态压缩到了一维。

这个化简化到了一定程度，题目就和具体数字彻底脱钩了。你会发现答案是“差值二进制里末尾有几个0”的函数，这也是为什么赛后大家把这道G题称为“数论题”。

3. 递推与结论：v2 才是那道题眼

3.1 定义 f(d) 并推递推式

定义 f(d) 表示两个边界相距 d 时，在这个间隙中可以生成的不同局部数组数量。边界本身不算在插入集合里，但最终数组一定包含两个边界值。为了讨论方便，当 d = 0 时，也就是两个边界相等，显然无法插入任何东西，f(0) = 1。

先看 d 是奇数的情况。比如 d = 1、3、5、7。此时区间中点是 x + d/2，一定不是整数，所以第一步操作都不可能发生，间隙始终保持原样。于是：

f(d) = 1，当 d 为奇数。

再看 d 是偶数的情况。设 d = 2m。第一步操作可以选择不做，这样局部状态就是“只包含两个边界”，对应 1 种情况；也可以选择插入中点。插入中点后，左右两个子区间长度都是 m，因为子区间完全独立，所以它们各自能产生 f(m) 种状态，组合起来是 f(m) * f(m) 种。

于是递推式就是：

f(d) = 1 + f(d/2)^2，当 d 为偶数且 d > 0。

这个递推很干净，但直接对每个差值算一遍递归，复杂度也不高，大概是 O(n log A)。不过这还不是最漂亮的结论。

3.2 把 f(d) 化简为 G[v2(d)]

观察上面的递推式，你会发现 f(d) 的取值其实只和目标 d 能被 2 整除多少次有关，也就是 d 的二进制表示里末尾 0 的个数，竞赛里常写成 v2(d)。

设 d = 2^k * q，其中 q 是奇数。那么第一次分裂后子区间长度是 2^(k-1) * q，第二次分裂后是 2^(k-2) * q，一直到第 k 次，子区间长度变成奇数 q，此时不能再分裂。在这个过程里，每一层的子区间数量会翻倍，但因为乘法原理，对称的子树状态数是一样的。

引入数组 G，其中 G[i] 表示“长度为 2^i 乘以任意一个奇数”的间隙的状态数。因为奇数部分不影响递归树的样子，所以：

G[0] = 1

G[i] = 1 + G[i-1]^2

最终 f(d) = G[v2(d)]。

前几项算出来是：

• G[0] = 1：差值奇数，不能操作。
• G[1] = 1 + 1^2 = 2：比如差值 2、6、10 等。
• G[2] = 1 + 2^2 = 5：比如差值 4、12、20 等。
• G[3] = 1 + 5^2 = 26：比如差值 8、24 等。
• G[4] = 1 + 26^2 = 677。

这个增长非常快，所以题目给出的答案一定会要求取模，否则状态数会变成天文数字。

3.3 多间隙合并：乘法原理

有了单个间隙的结论，整个数组就很简单了。把数组拆成 n-1 个相邻对，对每个相邻对计算差值 d_i = |a[i+1] - a[i]|，然后它的贡献是 G[v2(d_i)]。因为不同间隙互不影响，最终答案就是所有这些贡献的乘积，再对模数取余。

为什么可以乘而不是加？因为一个最终数组由所有间隙的局部状态共同决定。如果把每个间隙单独看成一个“角色”，选择不同局部状态就是给每个角色分配一个剧本，所有剧本拼起来得到完整数组。不同的分配方案一定产生不同的完整数组，所以总数就是乘法原理。

这里还有一个容易出错的细节：如果 d_i = 0，也就是相邻两个数相等，它们之间没有严格意义上的中点，操作也无法产生新的东西，贡献应当是 1。千万不要对它调用 v2 函数，因为 0 的二进制没有有限个末尾0的概念。

4. 代码实现与现场踩坑

4.1 完整 C++17 实现

核心代码非常短。预处理 G 数组，然后边读入边累乘答案即可。下面这份代码按多组测试数据来写，比较贴近区域赛题目的常见交互方式。

#include <bits/stdc++.h> using namespace std; using int64 = long long; const int64 MOD = 998244353; const int K = 64; int64 G[K]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); G[0] = 1; for (int i = 1; i < K; ++i) { G[i] = (1 + G[i - 1] * G[i - 1]) % MOD; } int T; cin >> T; while (T--) { int n; cin >> n; int64 ans = 1; int64 last = 0; for (int i = 0; i < n; ++i) { int64 x; cin >> x; if (i > 0) { int64 d = (x > last ? x - last : last - x); if (d == 0) continue; int k = __builtin_ctzll(d); ans = ans * G[k] % MOD; } last = x; } cout << ans << '\n'; } return 0; }

如果你不想用 GCC 内置函数__builtin_ctzll，也可以写一个手算 v2 的循环：

int k = 0; while ((d & 1) == 0) { ++k; d >>= 1; }

两种方式都行。手写循环的好处是任何编译器都能跑，不容易发生内置函数在极老环境下的兼容性问题。

4.2 为什么 G 数组只用预处理 64 项

比赛中数据范围通常不会让数组元素超过 1e18，那么任意相邻差值的绝对值也小于 2^63。一个 long long 最多有 63 个二进制位，所以 v2(d) 最大不会超过 62。预处理 64 项完全足够，既不会越界，也不会浪费空间。

即使把数据范围放宽到 1e9，k 也就 30 左右，预处理到 64 项毫无压力。关键是 G 的数值得按模数计算，否则 G[4] = 677 还好，G[5] = 458330 也还好，到 G[6] 直接变成十位数级别，G[7] 以上就会溢出 64 位整数，必须边算边取模。

这里提醒一下：G[i] 的递推式是 1 + G[i-1]^2，所以取模时是(1 + G[i-1] * G[i-1]) % MOD。乘法发生在取模之前，所以G[i-1]和G[i-1]相乘可能超过 64 位，但因为两个数都在 0 到 MOD-1 之间，乘积约 1e18 量级，long long 能安全装下。如果用 int 就会炸，这是新手最容易写错的地方。

4.3 我踩过的坑小结

第一个坑是差值取绝对值。C++ 里abs系列函数的行为在不同编译器下不太一致，直接用x - last可能变成负数，导致__builtin_ctzll结果完全错误。稳妥做法是手动判断大小，或者用llabs。千万不要对一个负数做位运算。

第二个坑是 d = 0。我一开始没有特判，直接调__builtin_ctzll(d)，函数对 0 的行为是未定义的，有时候返回 64，有时候返回 0，完全随机。后来改成先判断d == 0跳过，才稳定通过。

第三个坑是多组数据循环时忘记重置答案。因为答案是累乘，如果上一组样例的 ans 没有重置成 1，下一组样例就会从上一组的乘积继续乘，结果当然错。这种问题最好通过构造一个 n=1 的样例来验证，因为 n=1 时 ans 应该始终是 1。

第四个坑是递归写法导致爆栈。有些人会直接写一个递归函数算 f(d)，虽然深度最多几十层理论上不会爆栈，但如果递推式里反复计算相同状态，不加记忆化就会指数级爆炸。用 G 数组预处理是最不容易错的做法。

5. 小数据验证与边界用例

5.1 手算几个例子

理论推导再好，也建议用手算例子验证一遍，尤其是上考场前。

• 数组 [0,4]：只有一个间隙，d=4，v2(4)=2，答案 = G[2] = 5。这个和前面列的 5 种数组完全一致。
• 数组 [0,6]：d=6，v2(6)=1，答案 = G[1] = 2。实际只有两种：不插入，得到 [0,6]；插入中点 3，得到 [0,3,6]。
• 数组 [0,2,4]：两个间隙，差值都是 2，v2(2)=1，答案 = G[1] * G[1] = 4。实际四种情况是：不插、只插左中点的 1、只插右中点的 3、两边都插。
• 数组 [0,8]：d=8，v2(8)=3，答案 = G[3] = 26。这个数字看起来很大，但你如果画一棵深度为 3 的完全二叉树，会发现恰好就是“选择根节点、左子树状态、右子树状态”的所有组合。

这些例子都验证了公式是正确的。小数据验证最大的作用是帮你快速筛掉“忘记特判 d=0”或者“v2 算错”这类低级错误。

5.2 边界情况与性能表现

边界情况主要集中在数组长度小和差值极端这两类。

• n = 1：没有相邻对，答案就是 1。这符合直觉，因为没有任何操作可做。
• 所有相邻差值都是奇数：每个间隙都不能操作，答案还是 1。此时 G[0] = 1 保证了这一点。
• 差值特别大但 v2 很小：比如 d = 1000000000000000001，它是奇数，v2=0，贡献是 1，说明整个间隙完全无法扩展。
• 差值 2^k：贡献达到最大，因为递归树能完整展开 k 层。

性能方面，读入 O(n)，每个差值计算 v2 如果是内置函数就是 O(1)，预处理 G 数组是 O(64)，所以整体复杂度 O(n)。就算 n 开到 1e6，这份代码也跑得飞快。比赛时完全不需要担心通过时间，担心的是题目理解不到位。

6. 复盘：这题的核心方法论

6.1 打表找规律的真实过程

赛后我重新把思路过了一遍，发现真正让我卡住的不是代码，而是不愿意先做小规模暴力。如果一开始就写一个 20 行的 BFS，枚举所有小数组，把 f(1)、f(2)、f(3)、f(4)、f(6)、f(8) 打出来，数列应该是 1、2、1、5、2、26。看到这个序列，1、2、5、26 很容易联想到递推 x -> 1 + x^2，再验证奇数项都是 1，就能猜到“只和二进制尾部零有关”。

很多区域赛计数题其实都有这个套路：不要上来想高深结论，先暴力跑小数据，观察序列结构。如果序列满足某种自相似变换，那么大概率可以压缩成递归式。这题的递推式 1 + f(d/2)^2 就是典型自相似。

6.2 这类“无限操作计数”题的通用拆法

以后再遇到类似“可以无限次操作，问能得到多少种不同结果”的题，我建议按三步走。第一步，确认不同操作顺序是否会被视为同一结果，这决定了是计数还是数路径。第二步，寻找不变量或者结构分解，比如这题里的“间隙独立”就是结构分解。第三步，把过程画成树，用子树状态数合并，而不是去模拟整个状态空间。

Expanding Array 的核心其实就是一棵隐形的二叉树。每一个可插入点都对应二叉树上某个节点的位置，而每次操作只是在树上添加一个节点。既然所有可能状态就是这棵树的部分节点集合，那么计数自然变成“每个子树选或不选”的组合问题。想通这一点，代码量反而变得极简。

这类题目以后还会换个马甲出现，比如二维网格扩展、区间拆分、括号树等等。但只要记住这个“分裂成两半 -> 左右独立 -> 乘法原理”的模型，很多题都能套进去。这大概也算区域赛 G 题真正想考察的思维量吧。