题解：P16418 【MX-X28-T7】「FAOI-R12」副旋律

Adam_123 · 2026-11-13 14:20:25 · 题解

这是一篇简单易懂且详细的题解，只需要初中数学基础就可以理解。部分地方可能不严谨，比如用 f 指代函数值。

设 f(w_{1,2},w_{1,3},\dots,w_{1,n},w_{2,1},w_{2,3},\dots,w_{n,n-1}) 表示在 i\to j 边权为 w_{i,j} 的图中，所有强连通生成子图的权值之和。如果有重边，设边权分别为 a_1,a_2,\dots,a_k，那么在 f 中这些重边就等价于一个边权为 (\prod(a_i+1))-1 的边。

最终的答案要求对于每一条边分别求出包含这条边的强连通生成子图的权值之和，那么容斥一下就是所有强连通生成子图的权值之和减去不包含这条边的强连通生成子图的权值之和。不包含这条边就是把这条边删掉，剩下的图中所有强连通生成子图的权值之和。因此假设没有重边，那么边 u\to v 的答案即 f(w_{1,2},\dots,w_{u,v},\dots,w_{n,n-1})-f(w_{1,2},\dots,0,\dots,w_{n,n-1})。

我们分析一下 f 的性质，可以发现：如果对于 f 的除了 w_{i,j} 以外的自变量全都不变，将 f 函数写成 f_{\dots,w_{i,j-1},w_{i,j+1},\dots}(w_{i,j}) 的形式，那么此时 f 函数为一次函数。这一点比较显然，因为我们考虑将图中的 i\to j 边权增加 1，那么答案的增量就是原图中所有包含 i\to j 的强连通分量，计算边权之积时不算入 w_{i,j} 贡献的权制之和。由于我们固定了除了 w_{i,j} 以外的其他所有边权，所以这个增量就是一个定值。那么此时 f 就可以写成一次函数的形式了。

如果我们对于每一个 i\to j 都求出了这个增量，并且求出了 f(w_{1,2},\dots,w_{n,n-1})，那么自然就可以求出答案。因此我们考虑如何求出增量。

考虑将 f 函数展开，那么由于 f 对每个变量都是一次函数，所以展开式中不可能存在关于 w_{i,j} 的二次项。如果我们称这样的不存在二次项的形式为一种线性组合，那么 f 函数值就是自变量 w_{1,2},\dots,w_{n,n-1} 的线性组合。而我们计算 f(w_{1,2},\dots,w_{n,n-1}) 时，不是直接由这些边权值计算的，而是通过许多中间变量，这些中间变量都是更早计算的变量的线性组合。

考虑如果最终结果 f(w_{1,2},\dots,w_{n,n-1}) 是由 x_1,x_2,\dots,x_p 这些变量直接计算得到的，且是这些变量的一个线性组合，由于我们已知计算过程中任何中间变量的值，我们很容易就可以直接对于每个 x_i 计算出 f 对 x_i 的一次函数的斜率，即只将 x_i 增加 1 时答案的增量。比如 f=x_1x_2+x_3，那么我们在算 f 前 x_1,x_2,x_3 的值已经确定，并且我们知道具体的值。此时假设我们将 x_1 增加 1（不影响其他任何变量），那么 f'=(x_1+1)x_2+x_3，\Delta f=f'-f=x_2 可直接计算。同样的，假设我们将 x_2,x_3 分别增加 1，我们也可以求出对应的 f 的增量。

将更广泛地，如果我们的计算过程中计算了一个变量 x，x 是由若干个更早计算的变量 y_1,y_2,\dots,y_p 直接计算得到，且是这些变量的一个线性组合，那么如果我们已经求出 x 增加 1 对最终函数值的增量，且我们知道 y_1,y_2,\dots,y_p 的具体值，我们也可以直接得出 y_1,y_2,\dots,y_p 分别增加 1 对最终函数值的增量。还用上面那个例子，x=y_1y_2+y_3，那么 y_1 增加 1 时 \Delta x=y_2。而我们求出了 x 增加 1 时的 \Delta f_0，那么 x_1 增加 1 时 \Delta f=\Delta x\Delta f_0，可以直接求出。

这样的话，我们正着做一遍求出来 f(w_{1,2},\dots,w_{n,n-1}) 的值，并且记下所有中间变量在每一时刻的值，那么我们就可以按照时间顺序倒推出每个中间变量增加 1 对答案的增量。那么最终就可以推出对于每个 w_{i,j} 增加 1 对答案的增量，即我们的所求。如果有重边，答案即 f(w_{1,2},\dots,w_{u,v},\dots,w_{n,n-1})-f(w_{1,2},\dots,w_{u,v}',\dots,w_{n,n-1})，也是可以直接通过增量求的。

正着做就是 P11714 [清华集训 2014] 主旋律，这里不过多赘述了，只给出核心 dp 式子：

下面主要来说怎么倒着推增量。我们对于每一个变量，新开一个变量表示该位置增加 1 对答案的增量。考虑倒着做的时候，由于我们需要知道所有原变量在当前时刻的值，所以我们倒推的时候顺便把原变量做一遍逆操作作为时间倒流。下面逐一解释正着做时所有可能涉及到的操作以及如何倒着推增量。（下面的式子中如果 a 表示原变量，那么 A 就表示新开的记录增量的变量，且都在模意义下）

1. a += b