1. 7054题的标签拆解先把分治MTT优化dp翻译成人话多校赛第7场我是在补题时才认真看7054的题名叫 Yiwen with Formula。赛场上一扫标签分治MTT优化dp我没敢碰因为当时我对分治卷积这套组合的理解还停在背板子阶段。等到赛后静下来把题面翻译成递推式才意识到这题其实一点都不玄乎——它就是用CDQ分治去维护一个带卷积转移的DP只是因为最终答案要对一个非NTT友好的大质数取模所以被迫把NTT换成了MTT。题目名里那个 Formula 不是用来吓人的它就是指转移过程中要用到的那个距离相关的公式函数。先说这类题的常见抽象。很多计数DP最后都能写成下面这样设 dp[i] 表示处理到第 i 个元素时以 i 为结尾的合法方案数转移时所有 j i 都会给 dp[i] 贡献 dp[j] * w(i-j)w(k) 是题面给出的某种公式函数有时候 w(k) 可以直接预处理有时候却要依赖于之前算出来的 dp最终答案通常是 dp[n] 或 dp 数组的和。如果 w(k) 一开始就是已知数组理论上可以走生成函数求逆把 dp 和 w 都看成多项式解一个 (1 - W(x)) * D(x) base(x) 的方程多项式求逆一次就能把所有 dp 算出来。但这道题被标成分治MTT优化dp说明出题人大概率在某个环节堵死了一次性求逆的路逼着你按顺序边算边卷积。最典型的情况就是w(i-j) 不是一个只由 i-j 决定的固定数组或者说 dp 是一个带区间限制的二维状态又或者说模数根本不是 NTT 友好素数。无论哪种分治都能比全离线求逆更稳定地处理依赖顺序。朴素写法没什么好说的就是枚举所有 (j, i)操作数达到 n^2 量级。n 到 1e5 时哪怕不取模这个循环次数也已经让所有常数优化失去意义更别说每一轮还要做一次 64 位乘法和取模。真正有价值的是把枚举所有 j这个行为看成一整个卷积把 dp[j] 放到多项式的第 j 位把 w(k) 放到多项式的第 k 位两者做卷积后第 i 项恰好就是 sum_j dp[j] * w(i-j)。问题在于标准卷积会把左侧对右侧和右侧对左侧的贡献混在一起而我们这个递推有严格顺序右侧的 dp 还没算出来不能直接参与卷积。分治出来的原因就在这里把整个序列切成一块块区间每次只卷左块已知值对右块未知值的贡献再把这些贡献累加进去相当于把一次全局卷积切成了很多次局部卷积分批完成。理解到这一步原题在我心里就变成了一个半在线卷积模型dp 值的计算是根据当前已经知道的前缀逐步推进的推进方式就是 CDQ分治 卷积批量贡献。下面我按这个模型把原理、模板和抠细节的过程都记录一遍。2. 分治跑卷积的原理为什么左半边算完就能给右半边批发贡献2.1 CDQ 的主流程分治优化DP的代码骨架其实特别短void cdq(int l, int r) { if (l 1 r) return; int mid (l r) 1; cdq(l, mid); // 先递归算出左半边的 dp add_contribution(l, mid, r); // 把左半边对右半边的贡献批量加上 cdq(mid, r); // 再递归算右半边 }初看会有点懵右半边的 dp 不是还没算吗为什么可以先 add_contribution关键在这里——右半边的 dp 由两部分组成一部分是所有左侧元素对它的贡献另一部分是右半边内部相互转移产生的贡献。外层递归保证在进入 cdq(mid, r) 之前左侧所有该给的贡献都已经加到右半边的累加器里了。当递归到右半边内部时它再去处理右半边内部的转移。所以整个递归过程不会漏掉任何一对 (j, i)且每一对 (j, i) 恰好会在它们共同祖先区间的那个 add_contribution 中被处理一次。这个思路和 CDQ 分治解决三维偏序问题是一模一样的先处理左边区间内部的贡献再处理跨越左右两个区间的贡献最后处理右边区间内部的贡献。只不过在偏序问题里批量贡献用的是 BIT在这里批量贡献用的是卷积。2.2 批量贡献的一步卷积add_contribution 要做的事情是把所有 l j mid 的 dp[j] 对 mid i r 的 dp[i] 贡献一次性算完for (int i mid; i r; i) for (int j l; j mid; j) dp[i] dp[j] * w(i - j);朴素写是 O(len1 * len2)。但观察这个式子如果把 dp[j] 和 w(i-j) 分别看成两个多项式这本质上就是卷积。具体做法是构造多项式 A长度为 mid-lA[x] dp[lx]也就是把左半段的 dp 值放到从 0 开始的下标多项式 B长度为 r-lB[k] w(k)其中 k 从 0 到 r-l-1令 C A * B那么第 t 项就是 sum_{xyt} A[x] * B[y]。代入 x j-ly i-j得到 t (j-l) (i-j) i-l。也就是说卷积结果 C[t] 恰好等于 dp[lt] 从所有左侧 j 处收到的贡献。于是批量累加就一句话for (int i mid; i r; i) dp[i] C[i - l];为什么这里要用相对下标 A[x] dp[lx]因为 w 的下标表示距离距离不会被区间左端点平移。如果 A 直接按下标 j 存 dp[j]那 C 的 t 就变成了 j (i-j) i看起来更简单但只在 l0 时成立。一旦 l 不是 0A 中 dp[j] 的下标从 j 变成了 j-l卷积结果的下标也要跟着减 l。统一用相对下标可以避免在递归不同的 l 时反复写偏移修正。2.3 复杂度的直觉每次递归区间长度为 len卷积复杂度 O(len log len)分治递归树每一层所有区间卷积的总复杂度是 O(n log n)总共有 O(log n) 层所以整体是 O(n log^2 n)。n1e5 时大概需要 17 层的卷积过程。如果只是普通 NTT这个复杂度在多数 OJ 上是能过的但换成 MTT 后常数会明显变大所以要特别注意别在短区间上也做卷积。实际上递归到很小区间时比如区间长度小于 32 或 64直接双层循环暴力累加无论从代码简洁度还是从常数角度都比调用 MTT 划算。分治下一层有大量长度为 1、2、4、8 的小区间如果每个都走一遍 MTT光初始化多项式和变换长度对齐就会浪费大量时间。我后来把阈值设成了 64实测跑得快很多后面第 4 章的模板里也直接加入了这个小优化。3. MTT模块选型1e97模数下的三种暴力解法3.1 为什么不能直接NTT普通 NTT 要求在模数 P 下存在足够高阶的单位根。具体来说P 要能写成 c * 2^k 1 的形式并且 k 要大于等于卷积需要的 2 的幂次。998244353 就是这么来的998244353 - 1 119 * 2^23所以它能支持长度不超过 2^23 的卷积。但题目如果要求答案对 1e97 取模事情就麻烦了。1e97 - 1 2 * 500000003里面只有一个因子 2根本不存在长度为 2^k 的单位根没法直接用 NTT。这时候就需要 MT T来处理任意模数卷积。MTT 这个名字在不同选手嘴里可能指代不同方案常见的有三条路三模数 NTT选三个 NTT 友好素数分别做卷积再用中国剩余定理合并回原模数拆系数 FFT把每个数拆成高位低位用普通 FFT 做几次浮点乘法再还原分段卷积 long double FFT精度比 double 高一些配合拆系数也能做。我这里只详细说前两种因为它们在竞赛里最常用。3.2 三模数NTT的实现思路三模数 NTT 是我在 7054 上最终选择的方案。思路是选三个足够大的 NTT 友好素数使得任意两个输入系数相乘的结果不会超过三个素数乘积造成的精度盲区。常用的一组是模数阶数支持原根9982443532^23310045358092^2134697620492^263分别用这三个模数做同一组卷积得到三个余数结果 r1、r2、r3。真实卷积结果 X 在模 p1、p2、p3 下分别等于 r1、r2、r3。对于每一项可以用 CRT 求出 X 在模 p1p2p3 下的唯一值。由于真正的 X 不会超过 p1p2p3大多数情况下远远小于这个值就是精确整数最后再对原模数取模即可。CRT 合并时有个经典坑p1 * p2 * p3 大约是 4.7e26远超 long long 范围直接相乘会溢出。解决办法是使用 __int128或者在合并过程中每步都取模只保存余数。推荐先两两合并long long crt_merge(long long m1, long long a1, long long m2, long long a2) { // 求 x ≡ a1 (mod m1), x ≡ a2 (mod m2) __int128 inv mod_inv(m1 % m2, m2); __int128 t ((a2 - a1) % m2 m2) % m2; __int128 k t * inv % m2; __int128 x a1 m1 * k; return x % (m1 * m2); // 注意乘法可能溢出实际用 __int128 或特殊写法 }如果直接对三模数做完整 CRT 再取模可以用如下思路const long long P1 998244353; const long long P2 1004535809; const long long P3 469762049; const long long INV_P1_MOD_P2 15311432; // 需要求逆元得到 const long long INV_P1P2_MOD_P3 55490977; // 需要求逆元得到 long long crt3(long long r1, long long r2, long long r3, long long mod) { __int128 x1 r1 P1 * ((r2 - r1 P2) % P2) % P2 * INV_P1_MOD_P2 % P2; __int128 x2 (x1 % P3 P3) % P3; __int128 t3 ((r3 - x2 P3) % P3) * INV_P1P2_MOD_P3 % P3; __int128 res x1 (__int128)P1 * P2 * t3; return (long long)(res % mod); }注意这里所有减法都要先加上对应模数再取模否则 C 的负数取模会让你查错查到怀疑人生。另外三模数 NTT 的常数是普通 NTT 的三倍code 里要把 NTT 写成一个模板函数内部使用 P1/P2/P3 作为模数不能混用原题模数。3.3 拆系数FFT的取舍拆系数 FFT 把每个数拆成低 15 位和高 15 位相当于把模数为 1e97 的乘法拆成几次部分积。设 a a0 basea1b b0 baseb1其中 base 115那么a*b a0*b0 base*(a0*b1 a1*b0) base*base*(a1*b1)这样每一项的乘积都控制在 double 能稳定表示的范围内。实现上可以做 4 次 FFT也可以通过共用 DFT 优化到 3 次甚至 2 次。优点是常数比三模数 NTT 小缺点是 float 的精度问题非常折磨人。尤其在边界上出现接近 1e9 的系数时double 只有 53 位有效数字一旦大数相加产生进位误差结果可能差 1而差 1 在模意义下就是 WA。我的个人建议是如果只是为了应付比赛三模数 NTT 的思维负担小得多如果追求极限性能再单独维护一份拆系数模板平时多 stress test 几遍。3.4 我在7054最终选用的组合我在这题里没有直接在分治递归里跑三模数 NTT 做所有区间。我的最终方案是区间长度小于 64 时暴力区间长度大于 64 时如果模数是 998244353直接普通 NTT如果模数是 1e97才切换到三模数 NTT。这样既保证了模板的通用性又避免了小区间上 MTT 的巨大常数。7064 这种题的时间很紧如果每层分治都做三模数 NTT即使复杂度是 O(n log^2 n)常数也不一定压得住。这个阈值优化帮了大忙强烈建议所有写分治卷积的人默认加上。4. 核心模板与下标换算从CDQ骨架到可AC的代码4.1 一份带暴力阈值的主框架下面这段是我实际在分治 NTT 类题目里的通用骨架假设模数为 MODconst int MOD 1000000007; vectorint dp, w; // dp 是答案w 是转移公式 int n; void cdq(int l, int r) { if (r - l 64) { // 小区间暴力避免频繁卷积 for (int i l; i r; i) for (int j l; j i; j) dp[i] (dp[i] 1LL * dp[j] * w[i - j]) % MOD; return; } int mid (l r) 1; cdq(l, mid); // 左半区间 [l, mid) 对右半区间 [mid, r) 的贡献 vectorint A(mid - l), B(r - l, 0); for (int i l; i mid; i) A[i - l] dp[i]; for (int k 1; k r - l; k) B[k] w[k]; // B[0]0 防止自转移 vectorint C convolution(A, B, MOD); for (int i mid; i r; i) { dp[i] C[i - l]; if (dp[i] MOD) dp[i] - MOD; } cdq(mid, r); }这个框架的适用范围是线性半在线卷积也就是 dp 只依赖距离 i-j 的情况。如果题目里 w 还依赖 j 本身就不能这样直接把 A 系数乘进卷积需要另想办法。4.2 下标偏移再强调一次我每次给同学讲这段都要把下标单独拉出来说。看上面的代码A 的下标 0 对应 dp[l]B 的下标 k 对应 w[k]所以卷积 C[t] 计算的是C[t] sum_{xyt} dp[lx] * w[y]对于一个右半区间位置 i我们希望得到的是sum_{jl}^{mid-1} dp[j] * w[i-j]令 x j-ly i-j于是 t xy i-l。所以取 C[i-l] 就是对的。如果脑抽直接取 C[i]那等于把 w 的下标错误地当成了 j 与 i 的绝对值差在 l 不为 0 时全错。写递归时最好先在纸上把代入关系写一遍再落到代码里。4.3 卷积实现的选择与封装如果 MOD 是 NTT 友好模数convolution 函数内部直接调用普通 NTT 即可。但 7054 这类题的答案通常要模 1e97所以我把模板写成了下面这种形式vectorint convolution(vectorint a, vectorint b, int mod) { if (a.empty() || b.empty()) return {}; if (mod 998244353) return ntt_conv(a, b, mod); // 三模数 NTT auto r1 ntt_conv_mod(a, b, 998244353); auto r2 ntt_conv_mod(a, b, 1004535809); auto r3 ntt_conv_mod(a, b, 469762049); vectorint res(a.size() b.size() - 1); for (int i 0; i (int)res.size(); i) res[i] crt3(r1[i], r2[i], r3[i], mod); return res; }注意 ntt_conv_mod 内部用的模数是传入的那个素数计算过程中不能出现 MOD。很多人第一次写三模数 NTT 时习惯性把取模操作全写成 MOD结果 r1、r2、r3 三个结果全是错的。4.4 长度对齐与空区间NTT 模板通常要求长度是 2 的幂因此在 ntt_conv 内部需要把 a 和 b 的长度扩展到不小于 a.size()b.size()-1 的 2 的幂。如果调用方只传了很短的两个多项式扩展会很频繁但又因为阈值优化大多是长度还行的区间。另一个容易忽略的点当某个区间只有 0 个元素时不要调用卷积直接返回。比如 n1 时cdq(0,1) 一进来就触发 r-l64暴力循环不会执行问题不大。但如果把阈值去掉cdq(0,1) 的 mid0 会产生空区间卷积收到空 vector很可能越界。5. 补题实录五个把我送进WA的细节5.1 卷积结果只取前 r-l 项三模数 NTT 返回的结果长度是 A.size() B.size() - 1也就是 (mid-l)(r-l)-1。但我们需要用的只有 C[0..r-l-1] 这一部分对应 il 到 r-1 的贡献。第一次我图省事直接 for i0; iC.size(); i 把整个 C 全加到 dp 数组上。结果 dp 被塞进了大量越界数据和旧缓存答案立刻变成一团乱麻。正确做法是只取区间 [mid-l, r-l)而且每次取完就及时对 MOD 取模。如果你用的是全局 NTT buffer这个问题会更隐蔽buffer 里长度大于本次所需的部分可能残留上一次的数据这些幽灵值会被当成卷积结果取出来。所以我后来改成每次局部新建 vector虽然慢但换来的是不用反复清 buffer。5.2 B[0] 必须为 0转移式子里 j i所以距离 k i-j 至少是 1。构造 B 时如果直接用 w[0] 作为 B[0]那么当 t (j-l)(i-j) 恰好对应一个 ji 的假转移时C 里就会混入 dp[i]*w[0] 的贡献。当 w[0] 不为 0 时这就等于自己给自己加了非法值WA 得毫无道理。我的习惯是初始化 B 全 0然后从 k1 开始复制 w[k]保证 B[0] 恒为 0。5.3 分治顺序与 base 初始化有的题目 dp[i] 一开始不是 0而是有一个初始值 base[i]。分治过程里每次 add_contribution 只是往上叠加左侧贡献所以 dp 数组记得在主函数里先初始化为 base。我在补题时一开始把 dp 清零只在最后加了 base等于丢了一整块初始条件答案差了好几个数量级。正确顺序是初始化 dp 为 base然后 cdq(0,n)最后输出 dp[n] 或 sum。对于 base 也能贡献给后续状态的情况base 应该被当成 dp 的一部分参与分治所以它必须放在 dp 数组里一起卷积。5.4 CRT 合并的负数取模CRT 合并过程中有大量 (a2-a1)%p 这类式子。C 对负整数的取模结果是负数必须写成 ((a2-a1)%pp)%p。我建议封装一个 mod 函数所有取模一律走它long long mo(long long x, long long p) { x % p; if (x 0) x p; return x; }少了这一步r2-r1 为负时算出来的逆元乘数错乱最终结果可能变成一个负的随机数。这种 bug 不报 RE不报溢出就是答案错得毫无规律非常浪费时间。5.5 模数不同的 NTT 不能用同一套原根三模数 NTT 的三个模数原根都是 3这只是巧合。如果你换一组模数原根可能要重新求。我见过有人复用模板里的原根列表但中间的 len、逆元、原根幂次全都按 998244353 来算结果在做第二个模数时单位根本质上就错了。稳妥的做法是每个模数单独封装 NTT原根和 mod 一起传进函数不要默认原根就是 3。6. 分治MTT不只属于这一题可套用的DP套路6.1 半在线卷积模型把 7054 的抽象形式延展开几乎所有半在线风格的递推都能套这套框架。判别条件非常直接dp[i] base[i] sum_{ji} dp[j] * w(i-j)如果 w 能在分治过程中被计算或查询并且模数不友好那 CDQ MTT 就是标准解。这里唯一的区别是 w 是否与 j 无关。如果 w 只和距离 i-j 有关上面的代码原封不动可用如果 w 里还混着 j 的因子比如 w c^j * g(i-j)那就需要把 c^j 提进 A 数组再卷积这类变形我在别的计数题里也遇到过核心思想不变。6.2 二维区间DP的推广有些区间合并计数题会写成dp[l][r] sum_{kl}^{r-1} dp[l][k] * dp[k1][r] * F(r-l)这时候如果直接枚举 k是 O(n^3)。利用 CDQ 分治的外层区间切割把 l 和 r 中的一个维度当成左右区间的分治维度另一个维度的卷积就可以用 MTT 批量贡献。虽然复杂度通常会变成 O(n^2 log n)但对于 n500 或 n1000 的区间计数这个优化已经能把指数级的木桶效应打掉大半。我虽然没有在 7054 里实际验证这种扩展但它的原理和线性版本是完全一致的分治保证先后顺序卷积负责批量放量。6.3 你的板子库该放些什么经过 7054 这次补题我的板子库里现在固定放了两个卷积模板一个是普通 NTT直接给 998244353 使用一个是三模数 NTT CRT给任意模数使用。两个模板都封装成 vector convolution(vector a, vector b, int mod) 的形式调用方根本不用关心内部是 NTT 还是 MTT。而在分治 DP 模板里阈值暴力、B[0]0、只取有效卷积区间这三件事我会每次检查一遍因为它们是我踩坑踩得最狠的地方。顺带一提那天补完 7054 后我把自己常用的分治 NTT 代码重新整理了一遍把里面所有依赖全局数组的部分全部改成了 vector 局部变量。之后的几次训练里遇到带卷积的 DP 题我基本十分钟内就能把这个骨架搭完剩下时间全部拿来处理题目里的公式细节。你也该试试把这份模板沉淀成自己的。比如给 convolution 函数加一个参数区分是否使用三模数 NTT给 cdq 加一个阈值这些十几行的改动会让你的板子在关键时刻更好用。
