成都站的G题Expanding Array赛场上卡了我挺久。当时读题的感觉是操作很简单但能生成的数组数量好像会爆炸根本不敢往枚举方向想。赛后冷静下来重新推导才发现这题本质上是一道二叉树计数题核心结论甚至短到只剩一句话每个相邻间隙的贡献只由差值二进制末尾0的个数决定。如果你也是准备ICPC、CCPC或者各种区域赛的选手这题的思路很值得记一下。先说这题适合谁它适合已经能熟练写基础DP、图论模板但遇到“看似无限过程”的计数题容易慌的选手。题目给出的操作非常朴素难的是把“无限多中间状态”压缩成一个递推式。下面我按赛后复盘的顺序把题意、关键性质、递推推导、代码实现和现场踩过的坑全部拆开讲。1. 题意拆解一个看起来会爆炸的过程1.1 操作定义与“最终数组”题目给了一个长度为 n 的整数数组。你每次可以选择相邻的两个数 x 和 y要求它们中间能插入一个整数中点。更具体一点如果 x 和 y 奇偶性相同那么它们中间的那个整数就是 (xy)/2你可以把它插入到两者之间如果 x 和 y 奇偶性不同说明两者之间没有整数中点这次操作就无法进行。重复任意次操作之后问一共能得到多少种不同的数组。这个定义非常像“把一个区间不断对半细分”。比如数组 [0,4]0 和 4 都是偶数中间整数是 2所以可以先变成 [0,2,4]接下来 0 和 2 之间可以插入 12 和 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)如果它们之间还能插入那么能够插入的数是多少答案只有一个(LR)/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] 1G[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[i1] - a[i]|然后它的贡献是 G[v2(d_i)]。因为不同间隙互不影响最终答案就是所有这些贡献的乘积再对模数取余。为什么可以乘而不是加因为一个最终数组由所有间隙的局部状态共同决定。如果把每个间隙单独看成一个“角色”选择不同局部状态就是给每个角色分配一个剧本所有剧本拼起来得到完整数组。不同的分配方案一定产生不同的完整数组所以总数就是乘法原理。这里还有一个容易出错的细节如果 d_i 0也就是相邻两个数相等它们之间没有严格意义上的中点操作也无法产生新的东西贡献应当是 1。千万不要对它调用 v2 函数因为 0 的二进制没有有限个末尾0的概念。4. 代码实现与现场踩坑4.1 完整 C17 实现核心代码非常短。预处理 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 项完全足够既不会越界也不会浪费空间。即使把数据范围放宽到 1e9k 也就 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下一组样例就会从上一组的乘积继续乘结果当然错。这种问题最好通过构造一个 n1 的样例来验证因为 n1 时 ans 应该始终是 1。第四个坑是递归写法导致爆栈。有些人会直接写一个递归函数算 f(d)虽然深度最多几十层理论上不会爆栈但如果递推式里反复计算相同状态不加记忆化就会指数级爆炸。用 G 数组预处理是最不容易错的做法。5. 小数据验证与边界用例5.1 手算几个例子理论推导再好也建议用手算例子验证一遍尤其是上考场前。数组 [0,4]只有一个间隙d4v2(4)2答案 G[2] 5。这个和前面列的 5 种数组完全一致。数组 [0,6]d6v2(6)1答案 G[1] 2。实际只有两种不插入得到 [0,6]插入中点 3得到 [0,3,6]。数组 [0,2,4]两个间隙差值都是 2v2(2)1答案 G[1] * G[1] 4。实际四种情况是不插、只插左中点的 1、只插右中点的 3、两边都插。数组 [0,8]d8v2(8)3答案 G[3] 26。这个数字看起来很大但你如果画一棵深度为 3 的完全二叉树会发现恰好就是“选择根节点、左子树状态、右子树状态”的所有组合。这些例子都验证了公式是正确的。小数据验证最大的作用是帮你快速筛掉“忘记特判 d0”或者“v2 算错”这类低级错误。5.2 边界情况与性能表现边界情况主要集中在数组长度小和差值极端这两类。n 1没有相邻对答案就是 1。这符合直觉因为没有任何操作可做。所有相邻差值都是奇数每个间隙都不能操作答案还是 1。此时 G[0] 1 保证了这一点。差值特别大但 v2 很小比如 d 1000000000000000001它是奇数v20贡献是 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 题真正想考察的思维量吧。
成都站的G题Expanding Array赛场上卡了我挺久。当时读题的感觉是操作很简单但能生成的数组数量好像会爆炸根本不敢往枚举方向想。赛后冷静下来重新推导才发现这题本质上是一道二叉树计数题核心结论甚至短到只剩一句话每个相邻间隙的贡献只由差值二进制末尾0的个数决定。如果你也是准备ICPC、CCPC或者各种区域赛的选手这题的思路很值得记一下。先说这题适合谁它适合已经能熟练写基础DP、图论模板但遇到“看似无限过程”的计数题容易慌的选手。题目给出的操作非常朴素难的是把“无限多中间状态”压缩成一个递推式。下面我按赛后复盘的顺序把题意、关键性质、递推推导、代码实现和现场踩过的坑全部拆开讲。1. 题意拆解一个看起来会爆炸的过程1.1 操作定义与“最终数组”题目给了一个长度为 n 的整数数组。你每次可以选择相邻的两个数 x 和 y要求它们中间能插入一个整数中点。更具体一点如果 x 和 y 奇偶性相同那么它们中间的那个整数就是 (xy)/2你可以把它插入到两者之间如果 x 和 y 奇偶性不同说明两者之间没有整数中点这次操作就无法进行。重复任意次操作之后问一共能得到多少种不同的数组。这个定义非常像“把一个区间不断对半细分”。比如数组 [0,4]0 和 4 都是偶数中间整数是 2所以可以先变成 [0,2,4]接下来 0 和 2 之间可以插入 12 和 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)如果它们之间还能插入那么能够插入的数是多少答案只有一个(LR)/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] 1G[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[i1] - a[i]|然后它的贡献是 G[v2(d_i)]。因为不同间隙互不影响最终答案就是所有这些贡献的乘积再对模数取余。为什么可以乘而不是加因为一个最终数组由所有间隙的局部状态共同决定。如果把每个间隙单独看成一个“角色”选择不同局部状态就是给每个角色分配一个剧本所有剧本拼起来得到完整数组。不同的分配方案一定产生不同的完整数组所以总数就是乘法原理。这里还有一个容易出错的细节如果 d_i 0也就是相邻两个数相等它们之间没有严格意义上的中点操作也无法产生新的东西贡献应当是 1。千万不要对它调用 v2 函数因为 0 的二进制没有有限个末尾0的概念。4. 代码实现与现场踩坑4.1 完整 C17 实现核心代码非常短。预处理 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 项完全足够既不会越界也不会浪费空间。即使把数据范围放宽到 1e9k 也就 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下一组样例就会从上一组的乘积继续乘结果当然错。这种问题最好通过构造一个 n1 的样例来验证因为 n1 时 ans 应该始终是 1。第四个坑是递归写法导致爆栈。有些人会直接写一个递归函数算 f(d)虽然深度最多几十层理论上不会爆栈但如果递推式里反复计算相同状态不加记忆化就会指数级爆炸。用 G 数组预处理是最不容易错的做法。5. 小数据验证与边界用例5.1 手算几个例子理论推导再好也建议用手算例子验证一遍尤其是上考场前。数组 [0,4]只有一个间隙d4v2(4)2答案 G[2] 5。这个和前面列的 5 种数组完全一致。数组 [0,6]d6v2(6)1答案 G[1] 2。实际只有两种不插入得到 [0,6]插入中点 3得到 [0,3,6]。数组 [0,2,4]两个间隙差值都是 2v2(2)1答案 G[1] * G[1] 4。实际四种情况是不插、只插左中点的 1、只插右中点的 3、两边都插。数组 [0,8]d8v2(8)3答案 G[3] 26。这个数字看起来很大但你如果画一棵深度为 3 的完全二叉树会发现恰好就是“选择根节点、左子树状态、右子树状态”的所有组合。这些例子都验证了公式是正确的。小数据验证最大的作用是帮你快速筛掉“忘记特判 d0”或者“v2 算错”这类低级错误。5.2 边界情况与性能表现边界情况主要集中在数组长度小和差值极端这两类。n 1没有相邻对答案就是 1。这符合直觉因为没有任何操作可做。所有相邻差值都是奇数每个间隙都不能操作答案还是 1。此时 G[0] 1 保证了这一点。差值特别大但 v2 很小比如 d 1000000000000000001它是奇数v20贡献是 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 题真正想考察的思维量吧。
